best way to do "fermat" primalty checks

[Torbjorn Granlund]

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.

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.)

  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).

-- 
Torbjörn