Improvement to mpz_nextprime
Dan Oetting
dan_oetting at qwest.net
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