fft enhancement?

[Jason F]

I'm wondering if the FFT implemented in GMP would be suited for repeated squarings while remaining in the transform domain.

For instance, when calculating the Legendre symbol of, say [ x \ 8191], the normal method is to calculate x^4095 (mod 8191).  As an optimization, I personally would actually calculate x^4096 (mod 8191) to see if the result is x (which it will be if x is a quadratic residue mod 8191).  This amounts to repeatedly squaring "x" a total of 12 times (and taking the intermediate result mod 8191 to save memory).

Now instead of 8191, imagine some arbitrary large integer.  The repeated squaring step could be millions of iterations.  

I frankly don't know enough about FFTs in general to speak very intelligently about them or the specific properties of each type of transform.  But, from my understanding, a lot of the overhead comes from the transform and inverse transform.  If the repeated squaring can all take place in the transform domain without needing to do an inverse transform and then another forward transform in between, then surely a lot of processing can be saved.

Is this just a fantasy, or could it really be implemented?

-Jason



-------------- next part --------------
An HTML attachment was scrubbed...
URL: /list-archives/gmp-discuss/attachments/20040731/2b1874ba/attachment.htm