Great Internet Mersenne Prime Search

Great Internet Mersenne Prime Search

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 Internet PrimeNet Server that supports the research to demonstrate Entropia-distributed computing software, a company he founded in 1997. GIMPS is registered as Mersenne Research, Inc. Kurowski is Executive Vice President and board director of Mersenne Research Inc. GIMPS is said to be one of the first large scale distributed computing projects over the Internet for research purposes.[citation needed]

The project has found a total of thirteen Mersenne primes as of 9 November 2011 (2011 -11-09), eleven of which were the largest known prime number at their respective times of discovery. The largest known prime as of November 2011 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

History

The project began in early January 1996,[4][5] with a program that ran on i386 computers.[6][7] The name for the project was coined by Luther Welsh, one of its earlier searchers and the discoverer of the 29th Mersenne prime.[8] Within a few months, several dozen people had joined, and over a thousand by the end of the first year.[7][9] Joel Armengaud, a participant, discovered the primality of M1,398,269 on November 13, 1996.[10]

Status

As of September 2011, GIMPS has a sustained throughput of approximately 68 teraflops.[11] 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[12] if the software is used to discover a prime number with at least 100 million decimal digits and wins the $150,000 USD bounty offered by the Electronic Frontier Foundation.[13]

Primes found

All Mersenne 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. M40 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 20,996,011 have been checked twice.

Discovery date Prime Mq Digits count Name Mn Electronic machine platform
13 November 1996 M1398269 420,921 M35 Pentium (90 MHz)
24 August 1997 M2976221 895,932 M36 Pentium (100 MHz)
27 January 1998 M3021377 909,526 M37 Pentium (200 MHz)
1 June 1999 M6972593 2,098,960 M38 Pentium (350 MHz)
14 November 2001 M13466917 4,053,946 M39 AMD T-Bird (800 MHz)
17 November 2003 M20996011 6,320,430 M40 Pentium (2 GHz)
15 May 2004 M24036583 7,235,733 M41 ? Pentium 4 (2.4 GHz)
18 February 2005 M25964951 7,816,230 M42 ? Pentium 4 (2.4 GHz)
15 December 2005 M30402457 9,152,052 M43 ? Pentium 4 (2 GHz overclocked to 3 GHz)
4 September 2006 M32582657 9,808,358 M44 ? Pentium 4 (3 GHz)
23 August 2008 M43112609 12,978,189 M47 ? Core 2 Duo E6600 CPU (2.4 GHz)
6 September 2008 M37156667 11,185,272 M45 ?
12 April 2009 M42643801 12,837,064 M46 ? Intel Core 2 Duo (3 GHz)

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. If one were to print it out using standard printer paper, single-sided, it would require approximately 7 reams of paper.

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

References

  1. ^ GIMPS home page. Retrieved 16 September 2008.
  2. ^ Record 12-Million-Digit Prime Number Nets $100,000 Prize: Mersenne.org Wins EFF's Cooperative Computing Award
  3. ^ What are Mersenne primes? How are they useful? - GIMPS Home Page
  4. ^ http://www.garlic.com/~wedgingt/newsletters.html#9 The Mersenne Newsletter, Issue #9. Retrieved 2011-10-02.
  5. ^ http://www.mersenneforum.org/showpost.php?p=69824&postcount=3 Mersenne forum Retrieved 2011-10-02
  6. ^ 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. 
  7. ^ 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. 
  8. ^ The Mersenne Newsletter, Issue #9. Retrieved 2009-08-25.
  9. ^ Woltman, George (April 12, 1996). "The Mersenne Newsletter, issue #3" (txt). GIMPS. http://www.mersenne.org/newsletters/news3.txt. Retrieved 2009-06-16. 
  10. ^ Woltman, George (November 23, 1996). "The Mersenne Newsletter, issue #8" (txt). GIMPS. http://www.mersenne.org/newsletters/news8.txt. Retrieved 2009-06-16. 
  11. ^ PrimeNet Activity Summary, GIMPS, (updated automatically), http://www.mersenne.org/primenet/, retrieved 2011-09-19 
  12. ^ GIMPS Legalese, GIMPS, http://www.mersenne.org/legal/, retrieved 2011-09-19 
  13. ^ EFF Cooperative Computing Awards, Electronic Frontier Foundation, http://www.eff.org/awards/coop.php, retrieved 2011-09-19 

External links


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Great internet Mersenne prime search — Le Great Internet Mersenne Prime Search, ou GIMPS, est un projet de calcul partagé où les volontaires utilisent un logiciel client pour chercher les nombres premiers de Mersenne. Le projet a été fondé par George Woltman, qui est aussi le créateur …   Wikipédia en Français

  • Great Internet Mersenne Prime Search — (GIMPS, Gran búsqueda de números primos de Mersenne por Internet ) es un proyecto colaborativo de voluntarios que utilizan los programas gratuitos Prime95 y MPrime con el fin de buscar números primos de Mersenne. George Woltman ha fundado el… …   Wikipedia Español

  • Great Internet Mersenne Prime Search — Die Great Internet Mersenne Prime Search (GIMPS) ist ein gemeinschaftliches Projekt zur computergestützten Suche nach Mersenne Primzahlen. Das Projekt wurde von George Woltman gegründet, der auch die Software Prime95 und MPrime für das Projekt… …   Deutsch Wikipedia

  • Great Internet Mersenne Prime Search — Le Great Internet Mersenne Prime Search, ou GIMPS, est un projet de calcul partagé où les volontaires utilisent un logiciel client pour chercher les nombres premiers de Mersenne. Le projet a été fondé par George Woltman, qui est aussi le créateur …   Wikipédia en Français

  • Mersenne prime — Named after Marin Mersenne Publication year 1536[1] Author of publication Regius, H. Number of known terms 47 Conjectured number of terms Infinite …   Wikipedia

  • Mersenne prime — Nombre premier de Mersenne Marin Mersenne En mathématiques et plus précisément en arithmétique modulaire, un nombre premier de Mersenne est un nombre premier s écrivant sous la forme 2p 1, p étant premier. Ces nombres premiers doivent leur nom à… …   Wikipédia en Français

  • Prime number — Prime redirects here. For other uses, see Prime (disambiguation). A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is… …   Wikipedia

  • Mersenne-Primzahl — Poststempel mit der 23. Mersenne Primzahl, gefunden 1963 an der UIUC von Donald B. Gillies. Eine Mersenne Zahl ist eine Zahl der Form 2n − 1. Im Speziellen bezeichnet man mit Mn = 2n − 1 die n te Mersenne Zahl. Die ersten acht Mersenne Zahlen Mn… …   Deutsch Wikipedia

  • Mersenne-Primzahlen — Eine Mersenne Zahl ist eine Zahl der Form 2n − 1. Im Speziellen bezeichnet man mit Mn = 2n − 1 die n te Mersenne Zahl. Die Primzahlen unter den Mersenne Zahlen werden Mersenne Primzahlen genannt. Die ersten acht Mersenne Primzahlen Mp sind 3, 7,… …   Deutsch Wikipedia

  • Mersenne-Zahl — Eine Mersenne Zahl ist eine Zahl der Form 2n − 1. Im Speziellen bezeichnet man mit Mn = 2n − 1 die n te Mersenne Zahl. Die Primzahlen unter den Mersenne Zahlen werden Mersenne Primzahlen genannt. Die ersten acht Mersenne Primzahlen Mp sind 3, 7,… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”