2.On January 19, 2016, Dr. Curtis Cooper published about his recent discovery of
ID: 3679405 • Letter: 2
Question
2.On January 19, 2016, Dr. Curtis Cooper published about his recent discovery of a 49th Mersenne prime, 274207281 - 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 > 2, Mp 2 1 is prime if and only if 5-2 = 0, where So = 4 and, for k > 0, I give you two options: you may use either the grade school algorithm for multiplication or the Karatsuba algorithm. l arbitrarily chose the following two constants:Explanation / 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.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.