 |
 |
For two years, mathematicians throughout the world had been dreaming of discovering a 10 million digit prime number, a discovery which would allow them to claim the $100.000 award offered by the Electronic Frontier Foundation (EFF). The 44th Mersenne prime had been discovered in September 2006, and came tantalizingly close to qualifying for the award, with 9,808,358 digits. Since then, prime number enthusiasts had been holding their breath to see who would get the prize. Incredibly, the 45th and 46th Mersenne primes were discovered out of sequence and within two weeks of each other.
On August 23rd, Edson Smith discovered the 45th known Mersenne prime using a UCLA Mathematics Department's desktop computer: 243,112,609-1, a gigantic 12,978,189 digit number! And on September 6th, the 46th known Mersenne prime, 237,156,667-1, an 11,185,272 digit number, was found by Hans-Michael Elvenich, a prime number enthusiast from Langenfeld near Cologne, Germany! |
Both primes were independently verified by Tony Reix of the Bull Research Center in Grenoble, France using 16 1.6 GHz Intel® Itanium®2 CPUs of a Bull NovaScale 6160 HPC system and the multithreaded Glucas program.
What are Mersenne primes?
A Mersenne number is a positive integer that is one less than a power of two: Mq = 2q-1 where the exponent q is a prime. Since Mersenne primes are fairly rare, they are known by a “nickname” that indicates their ranking by size. For example, M31 = 231-1 (= 2.147.483.647) is called M8 because it is the 8th Mersenne prime, discovered by Euler in 1750. In 1876, M12 (a huge 39 digit number for the time!) was proved to be a prime by Edouard Lucas, using a revolutionary method that is still used today – but was manual at the time!
The search for Mersenne primes was revolutionized by the introduction of the computer. The first successful identification of a Mersenne prime by a computer was achieved in 1952 using the U.S. National Bureau of Standards Western Automatic Computer (SWAC) at UCLA, with a program written by Pr. Raphael Robinson. After a gap of 38 years during which no new Mersenne prime was discovered, the UCLA program allowed to identify five Mersenne primes within a few months.
Then 17 new Mersenne primes were identified until 1996.
Since 1996, the search for Mersenne primes has organized by GIMPS (Great Internet Mersenne Prime Search), a distributed computing project powered by volunteers and founded by George Woltman, who also wrote the prime testing software Prime95. 100.000 volunteers are contributing computing time – usually their personal computer’s idle time -- to the project, which distributes the exponents to be tested amongst the contributors. To this day, GIMPS has found a total of twelve Mersenne primes.
Once a contributor has found an exponent that gives a Mersenne prime, it must be verified twice, with a different program, on different hardware and by another person. This is how Bull’s Tony Reix came to be the first to verify M41, M42, M43 and M44, and came second for the verification of M45 and M46.
How long is the quest for Mersenne primes going to continue?
Are there more Mersenne primes to be found? Well, the set of Mersenne primes is probably infinite, like the number of ordinary primes, but this has never been proved. What is certain is they are getting harder to discover, first because they become rarer as their size increases, and second because the length of time necessary to test an exponent increases as the size of the tested exponents grows.
But then the number of GIMPS contributors is expanding, and processing power is also progressing fast with the availability of multicore architectures.
So this is not the end of the hunt for very large prime numbers. EFF has offered a $150,000 award for an immensely more difficult challenge: the discovery of the first 100-million-digit prime. When it will be discovered is anybody’s guess. Our expert Tony Reix’s forecast is that it will be found around 2020, and will be M50 or M51. Time – and available computing power – will tell…
|
