Improvement to mpz_nextprime
Paul.Zimmermann at loria.fr
Tue Jun 27 16:56:14 CEST 2006
> Date: Thu, 22 Jun 2006 20:45:16 -0600
> From: "Dan Oetting" <dan_oetting at qwest.net>
> 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
Interesting idea. However if K gets large I'm not sure it is possible
to find 2^(bits_per_limb * K) +/- Z which factors (almost) entirely into
More information about the gmp-discuss