Great Internet Mersenne Prime Search

Not to be confused with GIMP.
Great Internet Mersenne Prime Search (GIMPS)
Logo
Websitemersenne.org Edit this at Wikidata

The Great Internet Mersenne Prime Search (GIMPS) is a collaborative project of volunteers who use freely available software to search for Mersenne prime numbers.

GIMPS was founded in 1996 by George Woltman, who also wrote the Prime95 client and its Linux port MPrime. Scott Kurowski wrote the back end PrimeNet server to demonstrate volunteer computing software by Entropia, a company he founded in 1997. GIMPS is registered as Mersenne Research, Inc. with Kurowski as Executive Vice President and board director. GIMPS is said to be one of the first large scale volunteer computing projects over the Internet for research purposes.[1]

As of October 2024, the project has found a total of eighteen Mersenne primes, sixteen of which were the largest known prime number at their respective times of discovery. The largest known prime as of October 2024 is 2136,279,841 − 1 (or M136,279,841 for short) and was discovered on October 12, 2024, by Luke Durant.[2][3] On December 4, 2020, the project passed a major milestone after all exponents below 100 million were checked at least once.[4]

From its inception until 2018, the project relied primarily on the Lucas–Lehmer primality test[5] as it is an algorithm that is both specialized for testing Mersenne primes and particularly efficient on binary computer architectures. Before applying it to a given Mersenne number, there was a trial division phase, used to rapidly eliminate many Mersenne numbers with small factors. Pollard's p − 1 algorithm is also used to search for smooth factors.

In 2018, GIMPS adopted a Fermat primality test with basis a=3[6][7]as an alternative option for primality testing,[8] while keeping the Lucas-Lehmer test as a double-check for Mersenne numbers detected as probable primes by the Fermat test.[9] (While the Lucas-Lehmer test is deterministic and the Fermat test is only probabilistic, the probability of the Fermat test finding a Fermat pseudoprime that is not prime is vastly lower than the error rate of the Lucas-Lehmer test due to computer hardware errors.[10])

In September 2020,[11][12][13] GIMPS began to support primality proofs based on verifiable delay functions.[14] The proof files are generated while the Fermat primality test is in progress. These proofs, together with an error-checking algorithm devised by Robert Gerbicz, provide a complete confidence in the correctness of the test result and eliminate the need for double checks. First-time Lucas-Lehmer tests were deprecated in April 2021.[15]

GIMPS also has sub-projects to factor known composite Mersenne and Fermat numbers.[16]

  1. ^ "Volunteer computing". BOINC. Archived from the original on 18 December 2021. Retrieved 25 December 2021.
  2. ^ "GIMPS Discovers Largest Known Prime Number: 2136,279,841 − 1". Mersenne Research, Inc. 21 October 2024. Retrieved 21 October 2024.
  3. ^ "GIMPS Project Discovers Largest Known Prime Number: 282,589,933-1". Mersenne Research, Inc. 21 December 2018. Retrieved 21 December 2018.
  4. ^ "GIMPS Milestones Report". Mersenne.org. Mersenne Research, Inc. Retrieved 5 December 2020.
  5. ^ What are Mersenne primes? How are they useful? - GIMPS Home Page
  6. ^ a=2 wouldn't work as all Mersenne numbers are 2-pseudoprimes.
  7. ^ https://www.mersenneforum.org/node/22795
  8. ^ "GIMPS - the Math - PrimeNet".
  9. ^ "mersenneforum.org - View Single Post - Getting reliable LL from unreliable hardware". mersenneforum.org. Retrieved 2022-10-05.
  10. ^ "mersenneforum.org - View Single Post - Getting reliable LL from unreliable hardware". mersenneforum.org. Retrieved 2022-10-05.
  11. ^ "Announcements". GIMPS, the Great Internet Mersenne Prime Search. Archived from the original on 2021-08-14. Retrieved 1 September 2021.
  12. ^ "What's new". Retrieved 1 September 2021.
  13. ^ "Prime95 v30.3". Retrieved 1 September 2021.
  14. ^ Woltman, George (2020-06-16). "The Next Big Development for GIMPS". GIMPS forum. Retrieved 20 May 2022.
  15. ^ Woltman, George (2021-04-08). "First time LL is no more". Retrieved 19 May 2022.
  16. ^ "PrimeNet ECM Progress". Retrieved 20 May 2022.