Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
up vote 36 down vote accepted

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.

share|improve this answer
Wow, the failure rate of a probabilistic algorithm is lower than the failure rate of deterministic algorithm - because we're at the scale where calculations errors by hardware matter. Did I get that right? – Atte Juvonen 12 hours ago
Hard to say, when this happens precisely. As the probabilistic algorithm runs faster than the deterministic one, it is less likely disturbed by cosmic rays. – j.p. 3 hours ago
@j.p.: I compared in Python Maurer's algorithm with that of Miller-Rabin and found that they are quite comparable for practical purposes. See – Mok-Kong Shen 1 hour ago

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.

share|improve this answer
+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 new one (July 2013) is FIPS 186-4. – EBrown Jun 7 '15 at 13:29

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.

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.

share|improve this answer
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

There are some tests to determines whether a given number is prime, like Miller–Rabin primality test. These algorithms determine whether a given number is prime with probability P.

share|improve this answer

Instead of using probabilistic methods to generate large primes, as indicated in the other answers, one can (IMHO better) employ Maurer's algorithm of generating provable primes. I have a Python code implementing that algorithm, available at

share|improve this answer

What you could do, is use a Mill's constant for generation. Then, a test for primarity would be good anyways...(in case that not exact enough constant is chosen, so you could end up with non prime)

Mill's constant is such a number, that if powered to 3, and then powered to any N, where N is an usigned integer, we get value V wich, rounded down, is a prime.

So, let C be constant

C = 1.3063778838630806904686144926 ....

Then let

L = C^3

Then choose any N from <0, infinite> , N is whole

prime = round down( L^N )

It has several drawbacks, such as the constant must be very accurate, if you do not have accurate enough constant, you will end up with composed number. However, it is proven that this ,,algorithm" always generates prime numbers.

Next drawback I heard about is that as you increase the exponent, more computation power will be needed. However, all you need to do is generate two of them, so it could do...

For further reading, here is what I found as reference.

share|improve this answer
I wasn't aware that this was an industry standard method for generating primes for RSA; for one, it's not really an algorithm (that is, it isn't unless you give a precisely accurate value for Mill's constant), and in addition, it's not great at generating (say) 1024 bit primes (as it can, at best, produce only one prime of that size). – poncho Jun 18 at 18:55

protected by e-sushi 5 hours ago

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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