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

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

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

View all posts by Brent →

3 Responses to Mersenne primes and the Lucas-Lehmer test

stespenc83 says:

January 22, 2013 at 6:23 pm

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:
  
  January 22, 2013 at 8:46 pm
  
  Good question! I don’t know.
  - SB says:
    
    February 6, 2013 at 3:00 am
    
    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?