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

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?

• Your question is almost a duplicate of How can I generate large prime numbers for RSA? – mikeazo Feb 4 '12 at 14:32
• I was already aware of this question. However the answers to that question, whilst useful, didn't quite answer what I wanted to ask. My question was more on the theoretical side, whereas the other question was about implementing a specific algorithm. – VettelS Feb 4 '12 at 19:20
• Welcome to Cryptography Stack Exchange! I have changed your title to better capture the essence of your question (and make it more different to the question linked by Mikeazo), but feel free to edit it again. – Paŭlo Ebermann Feb 4 '12 at 21:18

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.

• Addition: method 1 can be expanded in a way that removes the bias noted in the last paragraph, by restricting to primes $p$ with $p\equiv b\bmod a$ for some fixed, secret and random $a$ and $b$ (with $a$ of known factorization). Sieving efficiency is kept. Also, that allows restricting to $p$ having $p-1$ and $p+1$ divisible by large primes, which improves resistance to some specialized factorization methods; this is required by FIPS 186 for RSA primes of 512 bits. – fgrieu Sep 4 '16 at 10:25
• @fgrieu: while that removes the specific bias listed, I don't know if it's been proven whether it still doesn't retain a bias. As for forcing $p-1$ and $p+1$ to have large factors, it does make some suboptimal factoring methods harder (where suboptimal means they're expected to take more time than, say, NFS even if we didn't do anything). – poncho Sep 6 '16 at 4:07

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/).