I wasn't sure if this question is more suited for SE.Math or not; please tell me if I should move it.
mpz_nextprime() function (find the next pseudoprime following the given number) GMP uses an interesting variation of the Sieve. In order to weed out multiples of small primes before applying slower tests (Miller-Rabin and Lucas), it first generates a table of residues of the "base" number. The base number can be thousands of bits long, but the residues are small since the primes are small. Then it iterates over small increments to the base number, only checking the
(increment + residue) mod prime instead of
base mod prime which would be much slower for a big
base. The algorithm can be seen here: https://github.com/alisw/GMP/blob/master/mpz/nextprime.c#L85
I have two questions regarding this algorithm:
- Does anyone know if it is a known method that can be attributed to some paper? I looked through different Sieve variations, but couldn't quite find a match.
- In the code, there is a limit on the maximum increment, after which a new prime is sampled and residues recalculated. It is described only as
#define INCR_LIMIT 0x10000 /* deep science */. I wonder, where does it come from? I would think that the only limit is when
increment + residueovershoots the data type size, which is 4 bytes (
unsigned), and the maximum
residueis about 1000, so there's still plenty of space left.