How to better generate large primes: sieving and then random picking or random picking and then checking?

Question

I'm writing an RSA algorithm, and am wondering what is the best and/or usual way to choose the initial prime numbers (p and q).

I know of two methods to achieve this, one based on a prime number sieve and another based on primality tests:

1. Use a prime sieve to find prime numbers within a random range, and then randomly pick a prime number from the output of the sieve.

2. Pick a number at random, and then test whether or not it is prime.

What is the best method, both from a security and efficiency perspective?

Answer 1

Both methods, of course, will work.

However, from an efficiency standpoint, (1) is considerably better. Here's why:

• The general strategy of both methods is to pick random numbers $R$, check to see that they have no small prime factors (smaller than a value $Q$), and then apply a rather expensive primality test (such as Miller-Rabin) to them.
• The probability of a random number $R$ that we have already tested to have no prime factors smaller than $Q<R$ is about $log(Q)/log(R)$, and hence the number of expensive primality tests we expect to need is about $log(R)/log(Q)$.

Now, with method 2, after we pick a number $R_1$ at random, you will check to make sure it has no small factors smaller than some $Q$. If it didn't, you'll run the expensive primality test on it, and if it wasn't prime, you'll go and pick another random number $R_2$ and try again, checking if that small number had no small factors. The key point is that the effort you put into checking whether number $R_1$ had factors smaller than $Q$ cannot be reused when checking number $R_2$. Therefore, we cannot make $Q$ that large (as we'll start spending a large amount of time just testing small factors).

On the other hand, with method 1, we set up a sieve that lists which numbers within the range have no factors smaller than some value $Q$, and then test those numbers that have no such factors. Here, we pick the first number $R_1$ within the sieve, and run the expensive primality test on it, and if it wasn't prime, we'll go to the second number with no small factors in the sieve. Here's the point: almost all the time taken in checking for small factors was taken setting up the sieve; once we've done that, going to the next number is essentially free. That is, this method gets to reuse the effort in checking our test numbers for small factors.

Because of this, we can make the value $Q$ in method 1 considerably larger before it starts to become counterproductive; and because of this larger $Q$ value, fewer of the expensive tests are needed.

Now, as for security; method (2) has the obvious advantage that each prime of the correct size will be chosen with exactly equal probability, while with method (1), primes that sit over a long sequence of composites will be chosen with somewhat greater probability. On the other hand, while (1) does choose primes with unequal probability, there's no know way that a factorization method can take advantage of that. Because of this, method (1) is considered safe.

Answer 2

If you look at 1024 bit numbers, about one in 700 is a prime. Eventually you check a prime, the effort for that is about 50 or 64 rounds of the Miller-Rabin test.

If you just pick random numbers, one round of Miller-Rabin filters out about 3/4ths of composite numbers, so you need 700 + 175 + 44 + 11 + 3 + 1 = 934 rounds to filter out the composite numbers.

If you just filter out multiples of 2, 3, 5 and 7, that leaves only 160 numbers with about 210 Miller-Rabin tests. If you create a sieve and remove all multiples of primes p <=P, that will reduce the number of Miller-Rabin tests but will cost for the sieving. You can experiment to find the optimal P.

Answer 3

A. J. Menezes et al., Handbook of Applied Cryptography (available online) 4.62 gives Maurer's algorithm for generating provable primes, which is fairly competitive in runtime with probabilistic methods (commonly employing Rabin-Miller test) for sizes of primes of practical interest. I have recently implemented Maurer's algorithm in Python (http://s13.zetaboards.com/Crypto/topic/7234475/1/).