best way to do "fermat" primalty checks
Décio Luiz Gazzoni Filho
decio at decpp.net
Mon Nov 14 04:38:19 CET 2005
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
More information about the gmp-discuss
mailing list