fast gcd

[Paul Zimmermann]

       Torbjörn,

> Other FFT variants use a fixed ring size (or a few fixed ring sizes to
> choose among).  The dyadic products will then take linear time.
> 
> This is an interesting resulting property: some FFT variants give
> different invariance behaviour.

indeed, and this means that the user might want different FFT variants,
depending on the application.

I can imagine applications where the user wants to minimize the time for the
pointwise products. Assume for example you want to multiply two k x k matrices
where each coefficient is a large integer. Each coefficient will be transformed
only once, but its Fourier transform will be multiplied k times. (With the fast
gcd we hit the case k=2.)

Are there applications where the user wants to minimize the time for the
Fourier transforms? I'm not sure, since each transform should be used at least
once to be useful.

Paul