The nth Mersenne number is
Mn = 2n – 1.
A Mersenne prime is a Mersenne number which is also prime. So far 50 have been found [1].
A necessary condition for Mn to be prime is that n is prime, so searches for Mersenne numbers only test prime values of n. It’s not sufficient for n to be prime as you can see from the example
M11 = 2047 = 23 × 89.
Lucas-Lehmer test
The largest known prime has been a Mersenne prime since 1952, with one exception in 1989. This is because there is an efficient algorithm, the Lucas-Lehmer test, for determining whether a Mersenne number is prime. This is the algorithm used by GIMPS (Great Internet Mersenne Prime Search).
The Lucas-Lehmer test is very simple. The following Python code tests whether Mp is prime.
def lucas_lehmer(p):
M = 2**p - 1
s = 4
for _ in range(p-2):
s = (s*s - 2) % M
return s == 0
Using this code I was able to verify the first 25 Mersenne primes in under 50 seconds. This includes all Mersenne primes that were known as of 40 years ago.
History
Mersenne primes are named after the French monk Marin Mersenne (1588–1648) who compiled a list of Mersenne primes.
Édouard Lucas came up with his test for Mersenne primes in 1856 and in 1876 proved that M127 is prime. That is, he found a 39-digit prime number by hand. Derrick Lehmer refined the test in 1930.
As of January 2018, the largest known prime is M77,232,917.
Related posts
[1] We’ve found 50 Mersenne primes, but we’re not sure whether we’ve found the first 50 Mersenne primes. We know we’ve found the 47 smallest Mersenne primes. It’s possible that there are other Mersenne primes between the 47th and the largest one currently known.
from Planet Python
via read more
No comments:
Post a Comment