In the previous post I mentioned that a particular Mersenne prime would be unsuitable for cryptography. In fact, *all* Mersenne primes are unsuitable for cryptography.

A prime number *p* is called “safe” if

*p* = 2*q* + 1

where *q* is also a prime. Safe primes are called safe because *p* − 1 does not have small factors (other than 2). The factors of *p* − 1 correspond to subgroups of the group used for encryption, and small groups can be exploited to attack encryption.

Mersenne numbers are numbers of the form

*M*_{n} = 2^{n} − 1.

Mersenne primes are Mersenne numbers that are also prime. A necessary condition for *M*_{n} to be prime is for *n* to be prime. This condition is not sufficient. For example,

2^{11} − 1 = 23 × 89.

But is necessary, for reasons we’ll get into shortly.

If *M*_{n} = 2*q* + 1, then *q* = *M*_{n−1}. But if *n* is a prime, then *n* − 1 is not a prime, with one exception: *n* = 3. So the only Mersenne prime that is a safe prime is *M*_{3} = 7, which is not a particularly large prime. Public key cryptography uses numbers in the thousands of digits, not single digits.

Why does *n* have to be prime before *M*_{n} stands a chance of being prime?

If *a* > 1, then *x*^{a} − 1 can be factored:

*x*^{a} − 1 = (*x* − 1)(*x*^{a−1} + *x*^{a−2} + … + 1)

If *n* can be factored into *ab*, then set *x* = 2^{b}. This shows that 2^{ab} − 1 has a factor, namely 2^{b} − 1.

In the previous post we said that *M*_{127} − 1 has a lot of small factors. We can find some of those factors easily:

*M*_{127} − 1 = 2 *M*_{126} = 2 (2^{126} − 1)

and (2^{126} − 1) is divisible by 2^{k} – 1 for every *k* that divides 126.

The nontrivial factors of 126 are 2, 3, 6, 7, 9, 14, 18, 21, 42, 63, and so 2^{k} – 1 is a factor of *M*_{126} for *k* equal to each of these numbers. This is enough to fully factor 2^{126} − 1 into

3³ × 7² × 19 × 43 × 73 × 127 × 337 × 5419 × 92737 × 649657 × 77158673929

given in the footnote from the previous post. You could easily come up with this factorization using pencil and paper, though it would not be easy to determine by hand that the last factor is a prime number.