Mersenne numbers, named after Marin Mersenne, are numbers of the form . The first few Mersenne numbers are therefore , , , , , and so on. Mersenne numbers come up all the time in computer science (for example, is the largest number which can be represented as a binary number with bits, since ).
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) .
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 is to have any chance of being prime, itself had better be prime too. In other words, if is composite, then so is . 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 is prime then so is . After all, , , , and are all prime. However, the next in the sequence fails: is not prime even though is.
So, if we have a prime number , then 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 , and for define . For example, when , we have
Finally, is prime if and only if . 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 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 :
ghci> filter lucasLehmer [2..100] [2,3,5,7,13,17,19,31,61,89]
Note that the largest Mersenne prime represented here, , 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 is not trivial either. We have to compute which requires doing the operation forty-three million times. Since we take the remainder mod 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 —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 then is prime.
Earlier, I posed the challenge of explaining why is composite if is composite. Here’s a hint (don’t read this unless you want a hint!): if is composite, then it’s possible to find another Mersenne number which divides .
Actually, this only works when , but that’s OK, we already know about !↩