# How can I generate large prime numbers for RSA?

What is the currently industry-standard algorithm used to generate large prime numbers to be used in RSA encryption?

I'm aware that I can find any number of articles on the Internet that explain how the RSA algorithm works to encrypt and decrypt messages, but I can't seem to find any article that explains the algorithm used to generate the p and q large and distinct prime numbers that are used in that algorithm.

-

The standard way to generate big prime numbers is to take a preselected random number of the desired length, apply a Fermat test (best with the base $2$ as it can be optimized for speed) and then to apply a certain number of Miller-Rabin tests (depending on the length and the allowed error rate like $2^{-100}$) to get a number which is very probably a prime number.

The preselection is done either by test divisions by small prime numbers (up to few hundreds) or by sieving out primes up to 10,000 - 1,000,000 considering many prime candidates of the form $b+2i$ ($b$ big, $i$ up to few thousands).

The deterministic prime number test by AKS is to my knowledge not yet used as it is slower and as the likeliness that an calculation error caused by the hardware is higher than $2^{-100}$.

Most smart cards offer a coprocessor for modular arithmetic with moduli from 1024 up to few thousand bits. The manufacturers often provide also libraries for RSA and RSA key generation using the coprocessor.

-

FIPS 186-3 tells you how they expect you to generate primes for cryptographic applications. It is essentially Miller-Rabin but it also specify what to do when you need extra properties from your primes.

-
+1 for mentioning FIPS, which is different than what most implementations use. –  samoz Jul 13 '11 at 13:26
FIPS 186-3 Appendix C , F –  ir01 Jul 13 '11 at 17:07

The problem of generating prime numbers reduces to one of determining primality (rather than an algorithm specifically designed to generate primes) since primes are pretty common: π(n) ~ n/ln(n).

Probabilistic tests are used (e.g. in java.math.BigInteger.probablePrime()) rather than deterministic tests. See Miller-Rabin.

http://en.literateprograms.org/Miller-Rabin_primality_test_%28Java%29

As far as primes for RSA goes, there are some additional minor requirements, namely that (p-1) and (q-1) should not be easily factorable, and p and q should not be close together.

-
Minor correction: the requirement isn't that p-1 (and q-1) shouldn't able to be easily factored; they could be twice a prime (and hence easily factorizable) without a problem. What they shouldn't be is smooth; that is, consist only of small (guessable) factors. –  poncho Aug 27 '11 at 1:14
Also, the "additional minor requirements" are automatically fulfilled by randomly generated primes (risks of hitting "bad primes" are much lower than, say, risks of having your PC munched to death by a crazed raccoon). Also, ECM factorization method can be seen as an extension of Pollard's $p-1$ method, against which you cannot defend with such tests, so you already rely on raccoon-sized low risks. –  Thomas Pornin Aug 30 '11 at 12:38