\ ******************************************************************* \ * * \ * 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-