Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
    
Why can't you use somes of the largest primes that fit in a 512 bit integer? –  user3997 Feb 8 '13 at 17:24
add comment

3 Answers

up vote 15 down vote accepted

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

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

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.

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

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/

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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