Great Internet Mersenne Prime Search
From Wikipedia, the free encyclopedia
The Great Internet Mersenne Prime Search (GIMPS) is a collaborative project of volunteers who use freely available computer software to search for Mersenne prime numbers. The project was founded by George Woltman, who also wrote the software Prime95 and MPrime for the project. Scott Kurowski wrote the PrimeNet server that supports the research to demonstrate Entropia-distributed computing software, a company he founded in 1997.
The project has found a total of thirteen Mersenne primes as of June 2009[update], eleven of which were the largest known prime number at their respective times of discovery. The largest known prime as of June 2009[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] This prime allowed GIMPS to win the $100,000 prize from Electronic Frontier Foundation for discovering a prime with more than 10 million decimal digits.[2] 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,[3] 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.
Contents |
[edit] History
The project began in January 1996, with a program that ran on 386 computers.[4][5] The name for the project was coined by Luther Welsh, one of its earlier searchers and the discoverer of the 29th Mersenne prime.[6] Within a few months, several dozen people had joined, and over a thousand by the end of the first year.[7][5] Joel Armengaud, a participant, discovered the primality of M1,398,269 on November 13, 1996.[8]
[edit] Status
As of November 2009[update], GIMPS has a sustained throughput of approximately 43 teraflops,[9] earning the GIMPS virtual computer a place among the most powerful computers in the world. As of mid-2008, this was approximately 30 teraflops; in mid-2006, 20 teraflops; and in early 2004, only 14.
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[10] 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.[11]
[edit] Primes found
All primes are in the form Mq, where q is the (prime) exponent. The prime number itself is 2q − 1, so the smallest prime number in this table is 21398269 − 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 13,466,917 have been checked twice.
| Discovery date | Prime | Digits | Name |
|---|---|---|---|
| 13 November 1996 | M1398269 | 420,921 | M35 |
| 24 August 1997 | M2976221 | 895,932 | M36 |
| 27 January 1998 | M3021377 | 909,526 | M37 |
| 1 June 1999 | M6972593 | 2,098,960 | M38 |
| 14 November 2001 | M13466917 | 4,053,946 | M39 |
| 17 November 2003 | M20996011 | 6,320,430 | M40 ? |
| 15 May 2004 | M24036583 | 7,235,733 | M41 ? |
| 18 February 2005 | M25964951 | 7,816,230 | M42 ? |
| 15 December 2005 | M30402457 | 9,152,052 | M43 ? |
| 4 September 2006 | M32582657 | 9,808,358 | M44 ? |
| 23 August 2008 | M43112609 | 12,978,189 | M47 ? |
| 6 September 2008 | M37156667 | 11,185,272 | M45 ? |
| 12 April 2009 | M42643801 | 12,837,064 | M46 ? |
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.
[edit] See also
- Mathematics
- List of distributed computing projects
- Distributed computing
- Berkeley Open Infrastructure for Network Computing
[edit] References
- ^ GIMPS home page retrieved 16 September 2008
- ^ Record 12-Million-Digit Prime Number Nets $100,000 Prize: Mersenne.org Wins EFF's Cooperative Computing Award
- ^ What are Mersenne primes? How are they useful? - GIMPS Home Page
- ^ Woltman, George (February 24, 1996). "The Mersenne Newsletter, issue #1" (txt). Great Internet Mersenne Prime Search (GIMPS). http://www.mersenne.org/newsletters/news1.txt. Retrieved 2009-06-16.
- ^ a b Woltman, George (January 15, 1997). "The Mersenne Newsletter, issue #9" (txt). GIMPS. http://www.mersenne.org/newsletters/news9.txt. Retrieved 2009-06-16.
- ^ The Mersenne Newsletter, Issue #9. Retrieved 2009-08-25.
- ^ Woltman, George (April 12, 1996). "The Mersenne Newsletter, issue #3" (txt). GIMPS. http://www.mersenne.org/newsletters/news3.txt. Retrieved 2009-06-16.
- ^ Woltman, George (November 23, 1996). "The Mersenne Newsletter, issue #8" (txt). GIMPS. http://www.mersenne.org/newsletters/news8.txt. Retrieved 2009-06-16.
- ^ PrimeNet Activity Summary, http://www.mersenne.org/primenet/, retrieved November 16, 2009
- ^ GIMPS prize terms, http://www.mersenne.org/prize.htm
- ^ Cooperative Computing Awards, http://www.eff.org/awards/coop.php
