best way to do "fermat" primalty checks

[Décio Luiz Gazzoni Filho]

On Nov 14, 2005, at 12:39 AM, Jim Fougeron wrote:

> Woltman would be the one to talk to about squaring and multiplying  
> in FFT in a modular world, but I am 90% sure that the FFT library  
> does not convert in/out of FFT space, until you need the "exact"  
> value (i.e. when done, or to save a resume file, where you need the  
> flat number).

I think you should double-check this claim. I would be extremely  
impressed to see something like that done. You can't do two  
multiplications in a row without propagating the carries, followed by  
either a modular reduction or a data rearrangement to fit into a  
larger transform vector; after a multiplication you're using almost  
all significant bits of the data and there's just not enough  
precision for a second multiplication. Now of course the standard  
method to propagate carries and do a modular reduction is to perform  
an inverse FFT first; I've never heard of a method to do either of  
these tasks in FFT space. If such methods exist, I'd be delighted to  
hear about them.

Now maybe he does something crazy like using a transform length  
bigger than the minimum required, while putting much smaller values  
in each transform element; I imagine that trick would allow for a few  
multiplications in a row without carry propagation, but increasing  
the length to avoid a smaller inverse transform is (to me at least) a  
net performance loss. And even then you can't postpone the inverse  
transform indefinitely: as each multiplication doubles the size of  
the data, even if you were to put a single bit per transform element,  
you would quickly reach the 53-bit mantissa of a double-precision  
floating value -- 5 is the limit, and given the space requirements  
for rounding error and the addition pyramid, maybe it won't even  
reach 5.

So, to wrap up: I don't think that's what Woltman does. I do agree he  
probably precomputes some data and keeps it in transform space, but  
he'll be forced to do FFTs (forward and inverse) periodically, though  
probably less often than what e.g. GMP does.

Décio
-------------- next part --------------
A non-text attachment was scrubbed...
Name: PGP.sig
Type: application/pgp-signature
Size: 186 bytes
Desc: This is a digitally signed message part
Url : http://gmplib.org/list-archives/gmp-discuss/attachments/20051114/769203b6/PGP-0001.bin