On January 19, 2016, Dr. Curtis Cooper published about his recent discovery of a
ID: 3676757 • Letter: O
Question
On January 19, 2016, Dr. Curtis Cooper published about his recent discovery of a 49th Mersenne prime, 2^74207281 - 1 (a number with 22,338,618 digits), as a result of a search executed by a GIMPS server network. The best method presently known for testing the primality of Mersenne numbers is the Lucas-Lehmer test. Specifically, it can be shown that for prime p greater then 2, M_p = 2^p - 1 is prime if and only if (S_p-2)%M_P=0, where S_0 = 4 and, for k greater then 0, S_k = ((S_k-1)^2-2)percent M_p. I give you two options: you may use either the grade school algorithm for multiplication or the Karatsuba algorithm. I arbitrarily chose the following two constants: time to add two numbers of 64 bits each: 0.5 nano-sec time to multiply two numbers of 64 bits each: 1.5 nano-sec. How much time would be required (on a single machine) to prove the primality of the 49th Mersenne prime? ( Proceed by making some reasonable assumptions about the recurrence expressing the running-time of both multiplication methods and solving them. ) Count time for subtraction to be the same as addition and the time for modulo (percent) to be the same as multiplicationExplanation / Answer
Mersenne Mp divides Sp-1 (where S1 = 4 and Sn = Sn-12-2), then Mp is prime.
The first thing to note is that if a Mersenne number Mn 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 Mn = 2^n - 1
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
This simple technique converges in at most 1 p-bit addition which can be done in linear time. This algorithm has a small exceptional case. It will produce 2n-1 for a multiple of the modulus rather than the correct value of 0. However, this case is easy to detect and correct.