7
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ Thank you very much for your answer! One follow-up question for clarity: when you say "candidate prime of prime+step", I'm assuming you mean some large, randomly generated odd number, added to whatever iteration you are in that stepping process (from 1 to 2000)? So you would go through those 2000 numbers and divide by each of the small primes, then do a Fermat test on the large numbers that aren't a multiple of the small primes? $\endgroup$ – Zach Dziura Oct 1 '15 at 4:46
  • 1
    $\begingroup$ @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 $\endgroup$ – poncho Oct 1 '15 at 12:45
  • 1
    $\begingroup$ @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. $\endgroup$ – poncho Oct 1 '15 at 12:58
  • $\begingroup$ Ahah! That makes a ton of sense! Thank you very much for your responses. $\endgroup$ – Zach Dziura Oct 1 '15 at 13:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.