# RSA primes vs. largest known primes

In the context of a new largest (mersenne) prime number being found this week -

The largest known prime number is now 2^57,885,161 − 1, and it took 5 years to find it since the last largest prime was found.

But we know that various asymmetric encryption algorithms require ridiculously large primes which are used as the infamous p and q factors. For example, 1024-bit RSA would require two 512-bit primes.

But this article, if correct, claims we are able to enumerate no more than ~1.7M prime numbers.

How does this settle with cryptographic prime number generation?

• Why can't you use somes of the largest primes that fit in a 512 bit integer? – user3997 Feb 8 '13 at 17:24

A Mersenne prime is a prime number that can be written in the form $M_p = 2^n-1$, and they’re extremely rare finds. Of all the numbers between 0 and $2^{25,964,951}-1$ there are 1,622,441 that are prime, but only 42 are Mersenne primes.

The second sentence is wrong.

What they meant to say is that there are 1,622,441 numbers of the form they mentioned in the first sentence below $2^{25,964,951}-1$.

There are 1,622,441 primes below 25,964,951 and thus 1,622,441 numbers of the form $2^p-1$ (with prime $p$) below $2^{25,964,951}-1$. See Wolfram Alpha.

There are over $2^{500}$ primes with exactly $2^{512}$ bits, so there are plenty to choose from for our RSA keys.

Take a look at the Prime number theorem which tells you that there are approximately $\frac{n}{\ln(n)}$ primes below $n$.

• Note that ArsTechnica has since tried to correct the article (and made it wrong in a different way). It now reads "Of all the numbers between 0 and 25,964,951 there are 1,622,441 that are prime, but only 42 are Mersenne primes". – poncho Feb 7 '13 at 20:43

In addition to RSA key generation often using probabilistic mechanism instead of proving p and q are prime, there are several other requirements, for instance p and q should not be too close.

In the context of Mersenne primes, it is worth noting that usually it is not preferable for either p or q to be Mersenne prime, i.e. for RSA key generation if using mechanism which proves primality of p or q, mechanisms that are only suitable for Mersenne primes shall be avoided.

The problem with Mersenne primes is that there are relatively few Mersenne primes, and thus factoring p or q becomes trivial.

• the problem with a Mersenne prime $p$ is that $p+1$ only has small factors, and this allows for faster factoring. Same holds when $p-1$ has lots of small factors as well. So in RSA keygeneration, such primes are not used, in the standard libraries.. – Henno Brandsma Feb 8 '13 at 22:27

It might be also worth noting that particular RSA implementations usually use some sort of sieve and primality test to get their primes. The steps usually are:

1. Generate as candidate a random odd number n of appropriate size.
2. Test n for primality.
• It is also possible to select an integer in such a way that deterministically proving its primality be efficient (general-purpose deterministic tests are kind of slow, but for instance knowing the factorization of $p - 1$ helps a lot) should you need that. Most cryptographic applications don't need to unconditionally guarantee the integer is prime (so they just pick at random) but sometimes a primality certificate may be desirable. – Thomas Feb 6 '13 at 14:47