best way to do "fermat" primalty checks

[Jim Fougeron]

Woltman would be the one to talk to about squaring and multiplying in FFT in a modular world, but I am 90% sure that the FFT library does not convert in/out of FFT space, until you need the "exact" value (i.e. when done, or to save a resume file, where you need the flat number).  When numbers get large, the timings between GMP and the woltman code do not even compare.  at 100k bits, GMP is probably 6 to 10 times slower.  At 500k bits, it is probably 100x slower (do not quote me on this, I have not run timing tests, but am pretty sure this is not too far from reality).  Also, I am pretty sure that in the Woltman FFT's, you are limited to an exponentiation base that is pretty small (8 bits is what is coded into PFGW, but I have been able to "get away with" up to 22 bits under certain conditions)

As for the reductions, I was refering to building reduction code for specific numeric "types", which does not translate into general purpose methods, like what would be needed for GMP.

For Mersenne/Fermat form of number, there is a well known "reductionless" method, the DWT.   What I was refering to, was direct O(n) reduction of other forms of numbers, such as k*b^n+-c, or binonmial, or other generalized forms which have "trick" methods of reduction perform a mod withouth reverting to division .   

However, for GMP, being that it is general purpose, adding these reduction methods may not be all that beneficial in the lib code.  However, if someone were to build them, and allow them to be "bolted" on as an extension to the mpz (or mpn) layer, and allow the code to be 


dec>   
dec>  On Nov 13, 2005, at 10:35 PM, Torbjorn Granlund wrote:
dec>  
dec>  > Jim Fougeron <jfoug at cox.net> writes:
dec>  >
dec>  >   1. FFT utilization.  The fastest way to do this, is to put all  
dec>  > variables
dec>  >   into FFT space, and build primatives which work in FFT space  
dec>  > (square,
dec>  >   mult, add reduction), so you never leave FFT until the final  
dec>  > answer is
dec>  >   given.  I believe (I could VERY rightly be wrong), that GMP is not
dec>  >   written this way, and does conversions into and out of FFT for each
dec>  >   squaring/mult.  That is why GMP does not scale well when moving  
dec>  > to HUGE
dec>  >   numbers.
dec>  >
dec>  > I'd really like to know how to compute an arbitrary mod in FFT space.
dec>  >
dec>  
dec>  Seconded, I'm not aware of any method that does this. Maybe he's  
dec>  talking about e.g. precomputing generalized inverses for Barrett  
dec>  reduction?
dec>  
dec>  > I don't think GMP's behaviour for HUGE numbers is affected by  
dec>  > wheather we
dec>  > convert froth and back into FFT space.  The problem might be with  
dec>  > memory
dec>  > locality of the present FFT code.  (We exnter and exit FFT space  
dec>  > not just
dec>  > for HUGE numbers, but for large numbers as well.)
dec>  >
dec>  
dec>  Keeping values in FFT space might be an interesting improvement,  
dec>  particularly in powering algorithms which perform a few  
dec>  precomputations and use them repeatedly throughout the algorithm.  
dec>  This could even be exposed to the programmer -- i.e. provide  
dec>  alternate functions for multiplication that can be performed in three  
dec>  steps:
dec>  
dec>  1. forward FFT
dec>  2. pointwise multiplication
dec>  3. inverse FFT and carry propagation
dec>  
dec>  Then, the programmer could save the work of a few FFTs. I understand  
dec>  this idea might not be welcome due to the mess it creates, though.
dec>  
dec>  >   2. Reduce the reduction.   If a special purpose modular reduction
dec>  >   can be acived, you can up to gain 3x speed improvement over
dec>  >   "standard" reduction methods.
dec>  >
dec>  > Not sure what you're takng about here.  Of course, reducing mod a
dec>  > Mersenne prime, or other close power-of-2, can be done with complexity
dec>  > O(n).
dec>  
dec>  Not only that, but Proth and Riesel primes as Jim mentioned. However,  
dec>  I'm also not sure what he means here -- Barrett reduction using  
dec>  Newton division, Montgomery reduction, or something else entirely?
dec>  
dec>  Request for more information seconded.
dec>  
dec>  Décio


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