best way to do "fermat" primalty checks

[Décio Luiz Gazzoni Filho]

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

> Jim Fougeron <jfoug at cox.net> 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  
reduction?

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

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.

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/b24a6b7e/PGP.bin