Improvement to mpz_nextprime

Dan Oetting dan_oetting at
Fri Jun 23 04:45:16 CEST 2006

A thought for improving the prime search: What if you pre-compute a  
set of composite trial divisors which are composed of disjoint sets  
of primes and have the form 2^(bits_per_limb * K) +/- Z where K  is  
about 2 and Z is a suitably small number that fits in a limb.  
Division by these composites should be quite fast and the residual  
can then be tested by division with each of the components.

The search for the suitable sets of primes could take a lot of  
computing but this only has to be done once.

-- Dan Oetting

More information about the gmp-discuss mailing list