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 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.
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] 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.
Contents |
[edit] History
The project began in January 1996, with a program that ran on 386 computers.[3][4] Within a few months, several dozen people had joined, and over a thousand by the end of the first year.[5][4] Joel Armengaud, a participant, discovered the primality of M1,398,269 on November 13, 1996.[6]
[edit] Status
As of July 2009, GIMPS has a sustained throughput of approximately 41[7] 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[8] 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.[9]
For free software alternatives, Glucas[10] and Mlucas[11] are both licensed under the GNU General Public License.
[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
- ^ 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 on 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 on 2009-06-16.
- ^ Woltman, George (April 12, 1996). "The Mersenne Newsletter, issue #3" (txt). GIMPS. http://www.mersenne.org/newsletters/news3.txt. Retrieved on 2009-06-16.
- ^ Woltman, George (November 23, 1996). "The Mersenne Newsletter, issue #8" (txt). GIMPS. http://www.mersenne.org/newsletters/news8.txt. Retrieved on 2009-06-16.
- ^ PrimeNet Activity Summary. Retrieved on 2009-07-10.
- ^ GIMPS prize terms
- ^ Cooperative Computing Awards
- ^ Glucas program
- ^ Mlucas program
