Lucas-Lehmer test

A primality test used to determine if a given number is a Mersenne prime.

Hmmm... the strings of random characters appearing in the chatterbox reveal that several readers have fallen asleep on their keyboards. If math doesn't do the trick, let's try greed:

this test can net you 100.000 $.

Now that I have your attention, let me explain.

A Mersenne prime is a number that can be expressed as M=2^P-1.

How can you tell if M is prime for a given P? Well, if P is not prime, then M won't be prime either. For all the other cases just follow these steps (this works for every P>2):

1. S₀=4
2. S_n=(S_n-1²-2) modulo (2^P-1)
3. repeat step 2 until you get S_P-2
4. if S_P-2 equals 0, M is prime

What? You want to know more about the money? Oh well...

Implement the algorithm in your favorite programming language. Choose P so that M will have more than 10 million digits. The Electronic Frontier Foundation offers an award to the discoverer of a ten million digit prime number.

(The catch is, state-of-the-art PCs will complete the test in about five months for any given P. The chances of M being prime are about 1 in 250.000. Still beats the lottery, though.)