\ *******************************************************************
\ * *
\ * New Mersenne Prime December 5, 2001 *
\ * *
\ *******************************************************************
New Mersenne Prime Announced December 5, 2001 - Today, the number
2^13,466,917 - 1 was announced to be a Mersenne prime, making it the
largest such number to be discovered to date. This news followed a
November 14 report to the mailing list of the GIMPS project that a
new unspecified Mersenne number had passed the Lucas-Lehmer test,
identifying it as a prime number. Mersenne numbers are numbers of the
form Mn = 2^n - 1. For example, M7 = 27 - 1 = 127 is a Mersenne
number. The study of such numbers has a long and interesting history,
and the search for Mersenne numbers that are prime (so-called
Mersenne primes) has been a computationally challenging exercise
requiring the world's fastest computers.
The complete list of indices n for previously known Mersenne primes
is given by
n = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279,
2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701,
23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433,
1257787, 1398269, 2976221, 3021377, and 6972593
(Sloane's A000043). The last of these has a whopping 2,098,960
digits. However, the region between the last two previously known
Mersenne primes has not been completely searched, so it is not known
if M6972593 is actually the 38th Mersenne prime. The five largest
known Mersenne primes have been discovered by an international
collaboration of volunteers known as the Great Internet Mersenne
Prime Search (GIMPS). The most recent prime was flagged by Michael
Cameron, a 20-year old Canadian GIMPS volunteer running George
Woltman's Prime95 computer program running on an x86-compatible PC.
The number flagged by Cameron was subsequently verified as prime by
independent software running on different hardware, leading to
today's official announcement of the new Mersenne prime. The new
Mersenne prime has 4,053,946 digits. ....
The Lucas-Lehmer test is
Let p > 3 be prime. Define a(1) = 4 and a(n+1) = a(n)^2 - 2 for m
>= 1. Then 2^p - 1 is prime if and only if 2^p - 1 divides
>a(p-1).
The sequence begins 4, 14, 194, 37634, 14 is divisible by 7 and
37634 by 31, so 7 and 31 are prime. Proofs can observe a(n) =
alpha^(2^n) + beta^(2^n) where alpha = sqrt(3/2) + sqrt(1/2) and beta
= sqrt(3/2) - sqrt(1/2). The hypothesis ensures 2 is a quadratic
residue modulo 2^p - 1 but 3 is a non-residue.
The values of a(n) can be reduced modulo 2^p - 1. Nonetheless, this
computation required 13 million squarings of 13-million-bit numbers.
Multiple implementations of the algorithm, on different
architectures, confirmed the result.
-30-