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 October2022[update], the project has found a total of seventeen Mersenne primes, fifteen of which were the largest known prime number at their respective times of discovery. The largest known primeas of September2022[ref] is 282,589,933−1 (or M82,589,933 for short) and was discovered on December 7, 2018, by Patrick Laroche.[2] On December 4, 2020, the project passed a major milestone after all exponents below 100 million were checked at least once.[3]
From its inception until 2018, the project relied primarily on the Lucas–Lehmer primality test[4] as it is an algorithm that is both specialized for testing Mersenne primes and particularly efficient on binarycomputer 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 as an alternative option for primality testing,[5][clarification needed] while keeping the Lucas-Lehmer test as a double-check for Mersenne numbers detected as probable primes by the Fermat test.[6] (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.[7])
In September 2020,[8][9][10] GIMPS began to support primality proofs based on verifiable delay functions.[11] 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.[12]
GIMPS also has sub-projects to factor known composite Mersenne and Fermat numbers.[13]
History
The project began in early January 1996,[14][15] with a program that ran on i386 computers.[16][17] The name for the project was coined by Luke Welsh, one of its earlier searchers and the co-discoverer of the 29th Mersenne prime.[18] Within a few months, several dozen people had joined, and over a thousand by the end of the first year.[17][19] Joel Armengaud, a participant, discovered the primality of M1,398,269 on November13,1996.[20] Since then, GIMPS has discovered a new Mersenne prime every 1 to 2 years on average. However, no new Mersenne prime has been found since 2018, constituting the longest period without a new discovery since the start of the project (over 5 years as of 2024).
Status
As of July2022[update], GIMPS has a sustained average aggregate throughput of approximately 4.71PetaFLOPS (or PFLOPS).[21] In November 2012, GIMPS maintained 95TFLOPS,[22] theoretically earning the GIMPS virtual computer a rank of 330 among the TOP500 most powerful known computer systems in the world.[23] The preceding place was then held by an 'HP Cluster Platform 3000 BL460c G7' of Hewlett-Packard.[24] As of July 2021 TOP500 results, the current GIMPS numbers would no longer make the list.
Previously, this was approximately 50TFLOPS in early 2010, 30TFLOPS in mid-2008, 20TFLOPS in mid-2006, and 14TFLOPS in early 2004.
Software license
Although the GIMPS software's source code is publicly available,[25] technically it is not free software, since it has a restriction that users must abide by the project's distribution terms.[26] Specifically, if the software is used to discover a prime number with at least 100,000,000 decimal digits, the user will only win $50,000 of the $150,000 prize offered by the Electronic Frontier Foundation.(On the other hand, they will win $3,000 when discovering a smaller prime not qualifying for the prize.)[26][27]
Third-party programs for testing Mersenne numbers, such as Mlucas[28] and Glucas[29] (for non-x86 systems), do not have this restriction.
GIMPS also "reserves the right to change this EULA without notice and with reasonable retroactive effect."[26]
Primes found
All Mersenne primes are of the form Mp = 2p − 1, where p is a prime number itself. The smallest Mersenne prime in this table is 21398269 − 1.
The first column is the rank of the Mersenne prime in the (ordered) sequence of all Mersenne primes;[30] GIMPS has found all known Mersenne primes beginning with the 35th.
^ †As of November14,2023[update], 65,723,341 is the largest exponent below which all other prime exponents have been checked twice, so it is not verified whether any undiscovered Mersenne primes exist between the 48th (M57885161) and the 51st (M82589933) on this chart; the ranking is therefore provisional. Furthermore, 114,055,847 is the largest exponent below which all other prime exponents have been tested at least once, so all Mersenne numbers below the 51st (M82589933) have been tested.[31]
^ ‡ The number M82589933 has 24,862,048 decimal digits. To help visualize the size of this number, if it were to be saved to disk, the resulting text file would be nearly 25 megabytes long (most books in plain text format clock in under two megabytes). A standard word processor layout (50 lines per page, 75 digits per line) would require 6,629 pages to display it. If one were to print it out using standard printer paper, single-sided, it would require approximately 14 reams (14 × 500 = 7000 sheets) of paper.
Whenever a possible prime is reported to the server, it is verified first (by one or more independent tests on different machines) before being announced. The importance of this was illustrated in 2003, when a false positive was reported to the server as being a Mersenne prime but verification failed.[32]
The official "discovery date" of a prime is the date that a human first noticed the result for the prime, which may differ from the date that the result was first reported to the server. For example, M74207281 was reported to the server on September 17, 2015, but the report was overlooked until January 7, 2016.[33]
In mathematics, a Mersenne prime is a prime number that is one less than a power of two. That is, it is a prime number of the form Mn = 2n − 1 for some integer n. They are named after Marin Mersenne, a French Minim friar, who studied them in the early 17th century. If n is a composite number then so is 2n − 1. Therefore, an equivalent definition of the Mersenne primes is that they are the prime numbers of the form Mp = 2p − 1 for some prime p.
A prime number is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways of writing it as a product, 1 × 5 or 5 × 1, involve 5 itself. However, 4 is composite because it is a product (2 × 2) in which both numbers are smaller than 4. Primes are central in number theory because of the fundamental theorem of arithmetic: every natural number greater than 1 is either a prime itself or can be factorized as a product of primes that is unique up to their order.
In mathematics, a Fermat number, named after Pierre de Fermat, the first known to have studied them, is a positive integer of the form
In mathematics, the Lucas–Lehmer test (LLT) is a primality test for Mersenne numbers. The test was originally developed by Édouard Lucas in 1878 and subsequently proved by Derrick Henry Lehmer in 1930.
Derrick Henry "Dick" Lehmer, almost always cited as D.H. Lehmer, was an American mathematician significant to the development of computational number theory. Lehmer refined Édouard Lucas' work in the 1930s and devised the Lucas–Lehmer test for Mersenne primes. His peripatetic career as a number theorist, with him and his wife taking numerous types of work in the United States and abroad to support themselves during the Great Depression, fortuitously brought him into the center of research into early electronic computing.
George Woltman is the founder of the Great Internet Mersenne Prime Search (GIMPS), a distributed computing project researching Mersenne prime numbers using his software Prime95. He graduated from the Massachusetts Institute of Technology (MIT) with a degree in computer science. He lives in North Carolina. His mathematical libraries created for the GIMPS project are the fastest known for multiplication of large integers, and are used by other distributed computing projects as well, such as Seventeen or Bust.
Prime95, also distributed as the command-line utility mprime for FreeBSD and Linux, is a freeware application written by George Woltman. It is the official client of the Great Internet Mersenne Prime Search (GIMPS), a volunteer computing project dedicated to searching for Mersenne primes. It is also used in overclocking to test for system stability.
In mathematics, a double Mersenne number is a Mersenne number of the form
In mathematics, the irrational base discrete weighted transform (IBDWT) is a variant of the fast Fourier transform using an irrational base; it was developed by Richard Crandall, Barry Fagin and Joshua Doenias in the early 1990s using Mathematica.
In number theory, a Wagstaff prime is a prime number of the form
John Lewis Selfridge, was an American mathematician who contributed to the fields of analytic number theory, computational number theory, and combinatorics.
Ralph Ernest Powers was an American amateur mathematician who worked on prime numbers.
The largest known prime number is 282,589,933 − 1, a number which has 24,862,048 digits when written in base 10. It was found via a computer volunteered by Patrick Laroche of the Great Internet Mersenne Prime Search (GIMPS) in 2018.
Riesel Sieve was a volunteer computing project, running in part on the BOINC platform. Its aim was to prove that 509,203 is the smallest Riesel number, by finding a prime of the form k × 2n − 1 for all odd k smaller than 509,203.
In mathematics, the Mersenne conjectures concern the characterization of a kind of prime numbers called Mersenne primes, meaning prime numbers that are a power of two minus one.
In mathematics, the Lucas–Lehmer–Riesel test is a primality test for numbers of the form N = k ⋅ 2n − 1 with odd k < 2n. The test was developed by Hans Riesel and it is based on the Lucas–Lehmer primality test. It is the fastest deterministic algorithm known for numbers of that form. For numbers of the form N = k ⋅ 2n + 1, either application of Proth's theorem or one of the deterministic proofs described in Brillhart–Lehmer–Selfridge 1975 are used.
In mathematics, the Pocklington–Lehmer primality test is a primality test devised by Henry Cabourn Pocklington and Derrick Henry Lehmer. The test uses a partial factorization of to prove that an integer is prime.
43,112,609 is the natural number following 43,112,608 and preceding 43,112,610.
This page is based on this Wikipedia article Text is available under the CC BY-SA 4.0 license; additional terms may apply. Images, videos and audio are available under their respective licenses.
