# Why does GnuPG save an array of remainders when generating prime numbers?

In looking at GPG's gen_prime() function, found within the cyphers/primegen.c file of libgcrypt, I noticed that the functions saves a list of the remainders from dividing the initial, randomly generated large number by the first 669 or so small prime numbers. What is the purpose of doing that? I don't see any reasoning behind doing so within the file.

What they're doing is doing a fast test to see if a candidate prime prime+step has any of the smallest 669 primes as a factor (by testing whether prime%p + step is a multiple of the small prime p. If they do find that the candidate has a small factor, then it is obviously not prime (and so they don't need to spend the comparatively long time running the Fermat test).
That being said, the code in primegen.c could have been done more efficiently. What is more usually done is creating a sieve; that is, you create an initially clear bitmap corresponding to the first (perhaps) 2000 entries of prime+step; for each small prime p, you compute prime%p, and based on that value, mark off every entry in the bitmap that corresponds to a multiple of p. Once you've done that, you can then step through the bitmask; any bit which is still clear corresponds to an entry with no small factors; you can then run your expensive primality tests on that. The advantage of this method is that you need to deal with each small factor only once; this means it is more effective to have far more small primes that you test against (and so you eliminate more composites during the cheap part of your primality search)
• @ZachDziura: actually, you would typically add twice the iteration (as there is little value even numbers. And, you don't divide each of the those numbers by each small prime (that's what you're trying to avoid); instead for each small prime $p$, you compute the initial candidate $prime % p$, and from that deduce which $prime+step$'s would be multiple of $p$. For example, if $p=3$ and $prime % p = 1$, then you know that $prime+2$, $prime+6$, $prime+10$, etc are multiples of 3; you can set those bits in the sieve – poncho Oct 1 '15 at 12:45
• @ZachDziura: the general formula is: if bit $i$ corresponds to the integer $ai+b$, then if $b % p = 0$, then set bits $kp$ (for integers $k$ in range), else if $a % p = 0$, then don't set any bits, else set bits $kp + p - (b a^{-1} \bmod p)$. Actually, if both $a % p = 0$ and $b % p = 0$, then no primes will be in range (as $ai + b$ will always be a multiple of $p$; presumably that'll never happen, as $a$ and $b$ must be relatively prime. – poncho Oct 1 '15 at 12:58