RSA primes vs. largest known primes

Question

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?

Answer 1

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$.

Answer 2

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.

Answer 3

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.
3. If n is composite, return to the first step.

The second step can be done with "true" or "probabilistic" tests. An interesting read is chapter 4 of the Handbook of Applied Cryptography: http://cacr.uwaterloo.ca/hac/