Mersenne primes and the Lucas-Lehmer test

Mersenne numbers, named after Marin Mersenne, are numbers of the form M_n = 2^n - 1. The first few Mersenne numbers are therefore M_0 = 0, M_1 = 1, M_2 = 3, M_3 = 7, M_4 = 15, and so on. Mersenne numbers come up all the time in computer science (for example, M_n is the largest number which can be represented as a binary number with n bits, since 2^0 + 2^1 + \dots + 2^{n-1} = M_n).

Last week was my birthday, and my age is now a Mersenne number! More excitingly, my age is a Mersenne number which is also prime. Prime Mersenne numbers are usually just called “Mersenne primes”, and they are of interest because it is much easier to test whether a given Mersenne number is prime than it is to test other, arbitrary numbers of the same size. This is the basis of the Great Internet Mersenne Prime Search, which I’ve written about on several occasions in the past (here, here, here, and here). The largest known prime is a Mersenne prime, namely (as of the time of this writing) 2^{43112609} - 1.

I’d like to explain how this actually works. Testing whether a Mersenne number is prime can be done using the Lucas-Lehmer test, named after its discoverers. Understanding how to carry out the Lucas-Lehmer test is actually incredibly simple, and I explain how it works below. Understanding why it works is more difficult, but I’ll try to explain (at least one direction of) the proof in a future post.

The Lucas-Lehmer test

The first thing to note is that if a Mersenne number M_n is to have any chance of being prime, n itself had better be prime too. In other words, if n is composite, then so is M_n = 2^n - 1. Why is that? Well, I’ll let you think about it, and reveal the solution in a future post. If you want a hint, there’s one at the end of this post.

You could be forgiven for thinking that the converse might be true as well: that is, if p is prime then so is M_p. After all, M_2 = 3, M_3 = 7, M_5 = 31, and M_7 = 127 are all prime. However, the next in the sequence fails: M_{11} = 2047 = 23 \times 89 is not prime even though 11 is.

So, if we have a prime number p, then M_p has a chance of being prime but it’s not guaranteed. How can we check? Here’s where the Lucas-Lehmer test comes in. It works like this: define s_0 = 4, and for k > 0 define s_k = (s_{k-1}^2 - 2) \bmod{M_p}. For example, when p = 5, we have

\begin{array}{rcl} s_1 &=& (4^2 - 2) \bmod{M_5} = 14 \bmod{31} = 14 \\ s_2 &=& (14^2 - 2) \bmod{31} = 8 \\ s_3 &=& (8^2 - 2) \bmod{31} = 0 \end{array}

Finally, M_p is prime if and only if s_{p-2} = 0. 1 That’s all! Here’s some Haskell code:

> -- A boring, dumb, slow, but obviously correct primality test: try
> -- dividing by 2 and by every odd number up to half the chosen number.
> isPrime :: Integer -> Bool
> isPrime 2 = True
> isPrime n = all (\d -> n `mod` d /= 0) (2 : [3, 5 .. n `div` 2])
> 
> -- Use the Lucas-Lehmer test to see whether 2^p - 1 is prime.
> lucasLehmer :: Integer -> Bool
> lucasLehmer 2 = True
> lucasLehmer p = isPrime p && s (p-2) == 0
>   where
>     mp  = 2^p - 1
>     s 0 = 4
>     s n = let s' = s (n-1) in (s'*s' - 2) `mod` mp

There are various tricks you can use to speed this up (for example, finding the remainder mod M_p can be done using some simple operations on binary numbers instead of actually doing division), but this is the basic idea. If you sign your computer up for GIMPS, this is what it’s computing!

Using the above code I can quickly (in a fraction of a second on my computer) find the exponents of all ten Mersenne primes smaller than M_{100}:

ghci> filter lucasLehmer [2..100]
  [2,3,5,7,13,17,19,31,61,89]

Note that the largest Mersenne prime represented here, M_{89} = 2^{89} - 1 = 618970019642690137449562111, is already pretty big! Testing whether this number is prime using the dumb isPrime algorithm would take like a trillion bazillion years.

Even using Lucas-Lehmer, testing numbers as big as M_{43112609} is not trivial either. We have to compute s_{43112607} which requires doing the operation x^2 - 2 forty-three million times. Since we take the remainder mod M_{43112609} at each step, the numbers involved will never get bigger than that, but that’s quite big enough—we’re talking about numbers that take about five megabytes to store! Usually when we say “five megabytes” we are thinking about really big images, or YouTube videos, but here we are talking about individual integers! So, you take a five-megabyte number, square it to get a ten-megabyte number, subtract two, reduce the result mod M_{43112609}—and then repeat 43 million times! Doing this requires many, many hours of computer time, even on the fastest modern computers. But the point is that it’s not even possible to contemplate doing this using a more brute-force method.

OK, that’s pretty cool, but why does it work? In a subsequent post or three I hope to present (at least a sketch of) a proof that if s_{p-2} = 0 then M_p is prime.

A hint

Earlier, I posed the challenge of explaining why 2^n - 1 is composite if n is composite. Here’s a hint (don’t read this unless you want a hint!): if n is composite, then it’s possible to find another Mersenne number which divides M_n.


  1. Actually, this only works when p > 2, but that’s OK, we already know about M_2!

About these ads
This entry was posted in arithmetic, computation, famous numbers, iteration, modular arithmetic, number theory, primes and tagged , , , , . Bookmark the permalink.

3 Responses to Mersenne primes and the Lucas-Lehmer test

  1. stespenc83 says:

    I solved for an equation that shows why the Mersenne number of a composite number must also be composite, but in looking at the factors of Mersenne numbers I noticed something that isn’t obvious from my equation, and I’m not sure if it holds for all Mersenne numbers or just the small ones that I tested.

    ***STOP reading if you don’t want any HINTS!***

    Okay, my equation shows that if a is any factor of n then M_a is a factor of M_n which is sufficient to show that M_n is not prime. However, what I noticed was that it seems if a_1, a_2, a_3, ... are distinct prime factors of n then \prod{M_{a_i}} can be factored from M_n. Do you know if this is always true? With my equation it is obvious for any n such that all M_{a_i} are also prime or share no prime factors. I’m just not sure that two composite Mersenne numbers from two different primes wouldn’t share a prime factor that wasn’t repeated in the Mersenne number of their product.

    I look forward to your future posts on the topic.

    • Brent says:

      Good question! I don’t know.

      • SB says:

        Is it too much of a hint to say “think in binary”?

        Here’s another hint. The decimal expansion of 1/p is periodic, a multiple of some number like 0.000100010001… where the number of 0′s between each 1 is one less than the period. That number is 1/999…9 for some number of 9′s. So 999…9/p is an integer: the repeating digit block in the decimal expansion. This means that every prime except 2 and 5 is a prime factor of 10^n - 1 for some n, and all its multiples.

        What is the equivalent for binary representation?

Comments are closed.