The Quest for Mersenne Primes
May 22, 2009, wasn't a particularly special date for most people, but there was good news once again from the mathematics world: we've found the 47th Mersenne prime, meaning $2^{42643801}-1$ is a prime number! The new prime was verified on June 12 by Tony Reix in France, and it is currently the second-largest known prime, with 12,837,064 digits! It was discovered through an international collaborative project called the "Great Internet Mersenne Prime Search" (GIMPS). Let's take a look back at this journey through the world of prime numbers together!
Primes / Mersenne Primes
Primes—now called "质数" in textbooks, though many mathematicians and enthusiasts still use the older term "素数" (perhaps it just sounds nicer)—are numbers that cannot be decomposed into a product of two smaller integers, such as 2, 3, 5, 7, and so on. Except for 2, every prime is odd.
Over 2000 years ago, the ancient Greek Pythagorean school proposed an interesting kind of number: one whose sum of all its factors (excluding the number itself) equals the number itself. Such numbers are called "perfect numbers," for example 6 = 1 + 2 + 3, where 1, 2, and 3 are all the factors of 6. Ever since then, this type of number has remained a fascinating subject passed down through the ages.
The great mathematician Euclid proposed a formula for constructing perfect numbers: $2^{p-1}(2^p-1)$, where $2^p-1$ is a prime number. Euclid probably never imagined that this formula would spark an enduring quest: the search for Mersenne primes of the form $2^p-1$. Of course, the first person to isolate and study primes of this particular form was the mathematician Mersenne, not Euclid. Nowadays, finding a Mersenne prime is equivalent to finding a perfect number, since no odd perfect number has ever been found, and among even perfect numbers, this is the only known form.
The Search Through History
However, the search for Mersenne primes has not been a smooth one. People discovered quite early on that for a prime of the form $2^p-1$, p itself must also be prime. This is because if p were composite, it could be written as p = ab, and then $2^{ab}-1=(2^a)^b-1=(2^b)^a-1$ would necessarily contain the factors $2^a-1$ and $2^b-1$.
But the converse of this theorem does not hold—that is, p being prime does not guarantee that $2^p-1$ is prime. For example, $2^{11}-1=23\cdot 89$. Worse still, such primes are exceedingly rare among the natural numbers. It wasn't until the year 1500 that the five Mersenne primes with p = 2, 3, 5, 7, 13 were found.
Later, famous mathematicians such as Fermat, Descartes, Leibniz, Euler, Goldbach, Lucas, Kraitchik, Cole, and Gillies all studied this type of prime. Marin Mersenne was among those with the most notable achievements, and so later generations named primes of the form "$2^p-1$" after him: Mersenne primes.
Proof / Primality Testing
The Lucas–Lehmer primality test is currently the best known method for testing the primality of Mersenne numbers.
The method was discovered by Édouard Lucas in 1878 and later improved by Lehmer in the 1930s, hence the name.
The method is based on computing a recursive sequence, and its principle is:
$M_p$ is prime if and only if $M_P$ divides $S_{n-2}(S_0=4,S_k = S_{k-1}^2-2,k > 0)$.
Suppose we want to verify that M3 = 7 is prime. We start with s = 4, and update it 3 - 2 = 1 time, taking each result modulo 7:
s ← ((4 × 4) - 2) mod 7 = 0
Since we end up with an s divisible by 7, M3 is prime.
On the other hand, M11 = 2047 = 23 × 89 is not prime. We again start with s = 4, and update it 11 - 2 = 9 times, taking each result modulo 2047:
s ← ((4 × 4) - 2) mod 2047 = 14
s ← ((14 × 14) - 2) mod 2047 = 194
s ← ((194 × 194) - 2) mod 2047 = 788
s ← ((788 × 788) - 2) mod 2047 = 701
s ← ((701 × 701) - 2) mod 2047 = 119
s ← ((119 × 119) - 2) mod 2047 = 1877
s ← ((1877 × 1877) - 2) mod 2047 = 240
s ← ((240 × 240) - 2) mod 2047 = 282
s ← ((282 × 282) - 2) mod 2047 = 1736
Since s is never divisible by 2047, M11 = 2047 is not prime. However, this test alone doesn't tell us the factors of 2047—we only learn its Lucas–Lehmer residue, 1736.
For $M_p$ (where p is prime), we have:
If a is a factor of $M_p$, then a has the following properties:
a ≡ 1 mod 2p
a ≡ ±1 mod 8
Searching / Computing
Mersenne primes may seem simple on the surface, but studying them is remarkably difficult. It requires not only deep theory and refined technique, but also enormous amounts of computation.
In late 1995 and early 1996, the American mathematician and programmer George Woltman wrote a program for computing Mersenne primes and made it freely available on the web to mathematicians and enthusiasts alike—this became the world-famous GIMPS project. The project uses distributed computing, harnessing the idle computational resources of countless ordinary computers to achieve computing power comparable to that of a supercomputer. The renowned British journal Nature once ran a report suggesting that the GIMPS project would not only further fuel enthusiasm for the search for Mersenne primes, but would also draw significant attention to research on distributed computing applications. In 1997, American mathematician and programmer Scott Kurowski and others created "PrimeNet," which automated the assignment of search ranges and the reporting of results back to GIMPS. Nowadays, anyone can join the GIMPS project and start searching for Mersenne primes simply by downloading the free Prime95 program from the GIMPS homepage.
www.mersenne.org - Official GIMPS website
www.mersenneforum.org - Official GIMPS forum
References:
http://songshuhui.net/archives/12950.html
Translated automatically with claude-sonnet-5; all equations are reproduced verbatim from the source. Copyright remains with the original author.