Great Internet Mersenne Prime Search

From Wikipedia, the free encyclopedia

Jump to: navigation, 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.

The project has found a total of thirteen Mersenne primes as of June 2009, eleven of which were the largest known prime number at their respective times of discovery. The largest known prime as of June 2009 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

[edit] References

  1. ^ GIMPS home page retrieved 16 September 2008
  2. ^ What are Mersenne primes? How are they useful? - GIMPS Home Page
  3. ^ 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. 
  4. ^ 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. 
  5. ^ Woltman, George (April 12, 1996). "The Mersenne Newsletter, issue #3" (txt). GIMPS. http://www.mersenne.org/newsletters/news3.txt. Retrieved on 2009-06-16. 
  6. ^ Woltman, George (November 23, 1996). "The Mersenne Newsletter, issue #8" (txt). GIMPS. http://www.mersenne.org/newsletters/news8.txt. Retrieved on 2009-06-16. 
  7. ^ PrimeNet Activity Summary. Retrieved on 2009-07-10.
  8. ^ GIMPS prize terms
  9. ^ Cooperative Computing Awards
  10. ^ Glucas program
  11. ^ Mlucas program

[edit] External links

Retrieved from "http://en.wikipedia.org/wiki/Great_Internet_Mersenne_Prime_Search"
Personal tools