Great Internet Mersenne Prime Search
The Great Internet Mersenne Prime Search (GIMPS) is a collaborative project of volunteers who use Prime95 and MPrime computer software that can be downloaded from the Internet for free in order to search for Mersenne prime numbers. The project was founded and the prime testing software was written by George Woltman. Scott Kurowski wrote the PrimeNet server that supports the research to demonstrate Entropia-distributed computing software, a company he founded in 1997.
This project has been successful: it has found a total of twelve Mersenne primes, each of which except for the latest one was the largest known prime at the time of discovery. The largest known prime as of October 2008[ref] is 243,112,609 − 1 (or M43,112,609 in short). This prime was discovered on 23 August 2008, by Edson Smith at the University of California, Los Angeles (UCLA)'s Mathematics Department.[1] Refer to the article on Mersenne prime numbers for the complete list of GIMPS successes.
To perform its testing, the project relies primarily on Édouard Lucas and Derrick Henry Lehmer's primality test,[2] an algorithm that is both specialized to testing Mersenne primes and particularly efficient on binary computer architectures. They also have a less expensive trial division phase, taking hours instead of weeks, used to rapidly eliminate Mersenne numbers with small factors, which make up a large proportion of candidates. John Pollard's p − 1 algorithm is also used to search for larger factors.
As of May 2008, GIMPS has a sustained throughput of approximately 29 teraflops, earning the GIMPS virtual computer a place among the most powerful supercomputers in the world.
Although the GIMPS software's source code is publicly available, technically it is not free software, since it has a restriction that users must abide by the project's distribution terms[3] if the software is used to discover a prime number with at least 100,000,000 decimal digits and wins the $150,000 bounty offered by the Electronic Frontier Foundation[4].
For free software alternatives, Glucas[5] and Mlucas[6] are both licensed under the GNU General Public License.
Primes found
All primes are in the form Mq, where q is the (prime) exponent. The prime number itself is 2q - 1, so the largest prime number in this table is 243112609 - 1.
Mn is the rank of the Mersenne prime based on its exponent. M39 is the largest Mersenne prime for which it is known that there is no other unknown Mersenne prime below with a lower exponent since all Mersenne numbers with prime exponent below 13466917 have been checked twice.
Discovery date | Prime | Digits | Name |
---|---|---|---|
6 September 2008 | M37156667 | 11185272 | M45 ? |
23 August 2008 | M43112609 | 12978189 | M46 ? |
4 September 2006 | M32582657 | 9808358 | M44 ? |
15 December 2005 | M30402457 | 9152052 | M43 ? |
18 February 2005 | M25964951 | 7816230 | M42 ? |
15 May 2004 | M24036583 | 7235733 | M41 ? |
17 November 2003 | M20996011 | 6320430 | M40 ? |
14 November 2001 | M13466917 | 4053946 | M39 |
1 June 1999 | M6972593 | 2098960 | M38 |
27 January 1998 | M3021377 | 909526 | M37 |
24 August 1997 | M2976221 | 895932 | M36 |
13 November 1996 | M1398269 | 420921 | M35 |
The number M43112609 has 12,978,189 digits. To help visualize the size of this number, a standard word processor layout (50 lines per page, 75 digits per line) would require 3,461 pages to display it.
Whenever a possible prime is reported to the server, it is verified first before it is announced. The importance of this was illustrated in 2003, when a false positive was reported to possibly be the 40th Mersenne prime but verification failed.
See also
- Mathematics
- List of distributed computing projects
- Distributed computing
- Berkeley Open Infrastructure for Network Computing
References
- ^ GIMPS home page retrieved 16 September 2008
- ^ What are Mersenne primes? How are they useful? - GIMPS Home Page
- ^ GIMPS prize terms
- ^ Cooperative Computing Awards
- ^ Glucas program
- ^ Mlucas program