best way to do "fermat" primalty checks

Décio Luiz Gazzoni Filho decio at
Mon Nov 14 01:56:38 CET 2005

On Nov 13, 2005, at 10:35 PM, Torbjorn Granlund wrote:

> Jim Fougeron <jfoug at> writes:
>   1. FFT utilization.  The fastest way to do this, is to put all  
> variables
>   into FFT space, and build primatives which work in FFT space  
> (square,
>   mult, add reduction), so you never leave FFT until the final  
> answer is
>   given.  I believe (I could VERY rightly be wrong), that GMP is not
>   written this way, and does conversions into and out of FFT for each
>   squaring/mult.  That is why GMP does not scale well when moving  
> to HUGE
>   numbers.
> I'd really like to know how to compute an arbitrary mod in FFT space.

Seconded, I'm not aware of any method that does this. Maybe he's  
talking about e.g. precomputing generalized inverses for Barrett  

> I don't think GMP's behaviour for HUGE numbers is affected by  
> wheather we
> convert froth and back into FFT space.  The problem might be with  
> memory
> locality of the present FFT code.  (We exnter and exit FFT space  
> not just
> for HUGE numbers, but for large numbers as well.)

Keeping values in FFT space might be an interesting improvement,  
particularly in powering algorithms which perform a few  
precomputations and use them repeatedly throughout the algorithm.  
This could even be exposed to the programmer -- i.e. provide  
alternate functions for multiplication that can be performed in three  

1. forward FFT
2. pointwise multiplication
3. inverse FFT and carry propagation

Then, the programmer could save the work of a few FFTs. I understand  
this idea might not be welcome due to the mess it creates, though.

>   2. Reduce the reduction.   If a special purpose modular reduction
>   can be acived, you can up to gain 3x speed improvement over
>   "standard" reduction methods.
> Not sure what you're takng about here.  Of course, reducing mod a
> Mersenne prime, or other close power-of-2, can be done with complexity
> O(n).

Not only that, but Proth and Riesel primes as Jim mentioned. However,  
I'm also not sure what he means here -- Barrett reduction using  
Newton division, Montgomery reduction, or something else entirely?

Request for more information seconded.


-------------- 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 :

More information about the gmp-discuss mailing list