Improvement to mpz_nextprime
Dan Oetting
dan_oetting at qwest.net
Tue Jun 27 19:54:12 CEST 2006
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
More information about the gmp-discuss
mailing list