Fwd: Re[2] : best way to do "fermat" primalty checks

[Jim Fougeron]

FYI,

----- 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[2]: best way to do "fermat" primalty checks

Hi Jim,

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.

Regards,
George 


Tray Helper - try to find something more useful... (http://www.trayhelper.com)