# 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? Commented Feb 4, 2012 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. Commented Feb 4, 2012 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. Commented Feb 4, 2012 at 21:18
• From prime number theorem and already said you have a probability in ratio of log . Choosing at random a number and check if it's prime also you can find in terms of coprime integers a probability involving the inverse of the zeta function for example .As independent variable you can now invokes Bernoulli's distribution . Look at : mathoverflow.net/questions/22953/… For a chapter concerning your question see p165: Davenport H (1999) The Higher Arithmetic: An Introduction to the Theory of Numbers, Cambridge University Press Commented May 17 at 12:33

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
Commented Sep 4, 2016 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). Commented Sep 6, 2016 at 4:07
• When you look at the time for filtering out composite numbers, remember that you have to test one real prime. So it is enough to make the test for composites fast compared to Miller-Rabin for a real probable prime. Miller-Rabin takes about 4/3 rounds on average for composite numbers. Commented May 15 at 17:45

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.

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

• If I give you a large number p and tell you “p is a prime, trust me”, then of course you don’t trust me. If I’m truthful then your cost is the cost of a successful primality test. But if you want a random prime, then your cost is the cost of one successful test, plus the cost of many many failed tests. So you’d want not to waste too much time on that. Commented May 13 at 7:47
• Now if you have a test that proves primality for a significant number of primes, that would be useful. For performance you would then also want to know how much time is spent on primes that the algorithm cannot prove to be prime. Commented May 13 at 8:01
• I looked at one of the papers quoted. Maurers algorithm generates primes. So I would be afraid that an attacker can generate the same primes. And it distinguishes “provable” primes. So using miller-Rabin to find a probable prime p, it seems we cannot determine that p is a proven prime in general. An algorithm that proves primality for a reasonable number of probable primes that it is given, that would be great. Commented May 15 at 17:38