Fwd: Re : best way to do "fermat" primalty checks
jfoug at cox.net
Mon Nov 21 14:18:11 CET 2005
----- Original Message -----
From: George Woltman <woltman at alum.mit.edu>
Recipient: jfoug at cox.net
Date and time: Sun, 20 Nov 2005 23:28:23 -0500
Subject: Re: Re: Re: best way to do "fermat" primalty checks
At 10:55 AM 11/14/2005, you wrote:
>The enclosed email was from a thread on the GMP mailing list.
It got here encrypted.
> I am under the assumption, that there is very little conversion
> in-out of FFT space within your lib to perform exponentations. Is
> that correct? I thought that a number was converted into FFT land,
> then all work (including reductions) was then done in the FFT, and
> conversions into and out of flat did not happen until a final
> result was needed (for whatever reason, like completion or
> intermediate saving).
>Am I totally off base with this assumption?
You are not entirely off-base. Obviously, we don't do an FFT, lots-of-squarings in
frequency space, inverse FFT. However, we do take a number that is already in
an array of doubles with the proper number of bits-per-limb, FFT, square, inverse
FFT, handle carries in the array-of-doubles so that another squaring
is ready to go.
Integrating gwnums with GMP is painful for any application that must
frequently convert from my array-of-doubles to GMP's array of longs. The
conversion code is slow.
Tray Helper - try to find something more useful... (http://www.trayhelper.com)
More information about the gmp-discuss