Improvement to mpz_nextprime

[Dan Oetting]

On Jun 27, 2006, at 8:56 AM, Paul Zimmermann wrote:

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

If the divisor is chosen to contain any small prime factor and K=2  
then testing for that factor reduces to about the cost of a scalar  
multiply with a short GCD on the 2 limb residual. The other factors  
in the divisor are a free bonus.

With limbs of only 32 bits it's not beyond our reach to search all  
such divisors with small values of K to see how much of a bonus can  
be realized and if there is enough of a bonus to be worth creating an  
optimized list of divisors.

-- Dan Oetting