Improvement to mpz_nextprime

[Paul Zimmermann]

> 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
small primes.

Paul Zimmermann