The Great Internet Mersenne Prime Search (GIMPS) is a collaborative project of volunteers who use freely available
software
Software is a set of computer programs and associated documentation and data. This is in contrast to hardware, from which the system is built and which actually performs the work.
At the lowest programming level, executable code consists ...
to search for
Mersenne prime
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 for some integer . They are named after Marin Mersenne, a French Minim friar, who studied them in the early 17t ...
numbers.
GIMPS was founded in 1996 by
George Woltman
George Woltman (born November 10, 1957) 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 Institu ...
, who also wrote the
Prime95
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 projec ...
client and its Linux port MPrime. Scott Kurowski wrote the back end PrimeNet
server
Server may refer to:
Computing
*Server (computing), a computer program or a device that provides functionality for other programs or devices, called clients
Role
* Waiting staff, those who work at a restaurant or a bar attending customers and su ...
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
Volunteer computing is a type of distributed computing in which people donate their computers' unused resources to a research-oriented project, and sometimes in exchange for credit points. The fundamental idea behind it is that a modern desktop co ...
projects over the Internet for research purposes.
, the project has found a total of seventeen Mersenne primes, fifteen of which were the
largest known prime number
The largest known prime number () is , 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.
A prime number is a posi ...
at their respective times of discovery. The largest known
prime
A prime number (or a prime) 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 ...
is 282,589,933 − 1 (or M82,589,933 for short) and was discovered on December 7, 2018, by Patrick Laroche. On December 4, 2020, the project passed a major milestone after all exponents below 100 million were checked at least once.
From its inception until 2018, the project relied primarily on the Lucas–Lehmer primality test as it is an
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
that is both specialized for testing Mersenne primes and particularly efficient on
binary
Binary may refer to:
Science and technology Mathematics
* Binary number, a representation of numbers using only two digits (0 and 1)
* Binary function, a function that takes two arguments
* Binary operation, a mathematical operation that ta ...
computer architecture
In computer engineering, computer architecture is a description of the structure of a computer system made from component parts. It can sometimes be a high-level description that ignores details of the implementation. At a more detailed level, t ...
s. Before applying it to a given Mersenne number, there was a
trial division
Trial division is the most laborious but easiest to understand of the integer factorization algorithms. The essential idea behind trial division tests to see if an integer ''n'', the integer to be factored, can be divided by each number in turn ...
phase, used to rapidly eliminate many Mersenne numbers with small factors. Pollard's ''p'' − 1 algorithm is also used to search for
smooth
Smooth may refer to:
Mathematics
* Smooth function, a function that is infinitely differentiable; used in calculus and topology
* Smooth manifold, a differentiable manifold for which all the transition maps are smooth functions
* Smooth algebrai ...
factors.
In 2018, GIMPS adopted the
Fermat primality test
The Fermat primality test is a probabilistic test to determine whether a number is a probable prime.
Concept
Fermat's little theorem states that if ''p'' is prime and ''a'' is not divisible by ''p'', then
:a^ \equiv 1 \pmod.
If one wants to tes ...
as an alternative option for primality testing, while keeping the Lucas-Lehmer test as a double-check for Mersenne numbers detected as
probable prime
In number theory, a probable prime (PRP) is an integer that satisfies a specific condition that is satisfied by all prime numbers, but which is not satisfied by most composite numbers. Different types of probable primes have different specific con ...
s by the Fermat test. (While the Lucas-Lehmer test is deterministic and the Fermat test is only probabilistic, the probability of the Fermat test finding a
Fermat pseudoprime
In number theory, the Fermat pseudoprimes make up the most important class of pseudoprimes that come from Fermat's little theorem.
Definition
Fermat's little theorem states that if ''p'' is prime and ''a'' is coprime to ''p'', then ''a'p''− ...
that is not prime is vastly lower than the error rate of the Lucas-Lehmer test due to computer hardware errors.)
In September 2020, GIMPS began to support primality proofs based on verifiable delay functions. 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.
GIMPS also has sub-projects to factor known composite Mersenne and
Fermat number
In mathematics, a Fermat number, named after Pierre de Fermat, who first studied them, is a positive integer of the form
:F_ = 2^ + 1,
where ''n'' is a non-negative integer. The first few Fermat numbers are:
: 3, 5, 17, 257, 65537, 42949672 ...
s.
History
The project began in early January 1996, with a program that ran on
i386
The Intel 386, originally released as 80386 and later renamed i386, is a 32-bit microprocessor introduced in 1985. The first versions had 275,000 transistors
The name for the project was coined by Luke Welsh, one of its earlier searchers and the co-discoverer of the 29th Mersenne prime.
Within a few months, several dozen people had joined, and over a thousand by the end of the first year.
Joel Armengaud, a participant, discovered the primality of M1,398,269 on November 13, 1996.
Status
, GIMPS has a sustained average aggregate
throughput
Network throughput (or just throughput, when in context) refers to the rate of message delivery over a communication channel, such as Ethernet or packet radio, in a communication network. The data that these messages contain may be delivered ov ...
of approximately 4.71 PetaFLOPS (or PFLOPS). In November 2012, GIMPS maintained 95 TFLOPS, theoretically earning the GIMPS virtual computer a rank of 330 among the
TOP500
The TOP500 project ranks and details the 500 most powerful non-distributed computing, distributed computer systems in the world. The project was started in 1993 and publishes an updated list of the supercomputers twice a year. The first of these ...
most powerful known computer systems in the world. The preceding place was then held by an 'HP Cluster Platform 3000 BL460c G7' of
Hewlett-Packard
The Hewlett-Packard Company, commonly shortened to Hewlett-Packard ( ) or HP, was an American multinational information technology company headquartered in Palo Alto, California. HP developed and provided a wide variety of hardware components ...
. As of July 2021 TOP500 results, the current GIMPS numbers would no longer make the list.
Previously, this was approximately 50 TFLOPS in early 2010, 30 TFLOPS in mid-2008, 20 TFLOPS in mid-2006, and 14 TFLOPS in early 2004.
Software license
Although the GIMPS software's
source code
In computing, source code, or simply code, is any collection of code, with or without comments, written using a human-readable programming language, usually as plain text. The source code of a program is specially designed to facilitate the wo ...
is publicly available, technically it is not
free software
Free software or libre software is computer software distributed under terms that allow users to run the software for any purpose as well as to study, change, and distribute it and any adapted versions. Free software is a matter of liberty, no ...
, since it has a restriction that users must abide by the project's distribution terms.
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
The Electronic Frontier Foundation (EFF) is an international non-profit digital rights group based in San Francisco, California. The foundation was formed on 10 July 1990 by John Gilmore, John Perry Barlow and Mitch Kapor to promote Internet ci ...
.
Third-party programs for testing Mersenne numbers, such as Mlucas and Glucas (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''.''"
Primes found
All Mersenne primes are of the form , where ''p'' is a prime number itself. The smallest Mersenne prime in this table is
The first column is the rank of the Mersenne prime in the (ordered)
sequence
In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is calle ...
of all Mersenne primes; GIMPS has found all known Mersenne primes beginning with the 35th.
, 61,809,281 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, 110,194,351 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.
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
A word processor (WP) is a device or computer program that provides for input, editing, formatting, and output of text, often with some additional features.
Word processor (electronic device), Early word processors were stand-alone devices ded ...
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.
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.
See also
*
Berkeley Open Infrastructure for Network Computing
The Berkeley Open Infrastructure for Network Computing (BOINC, pronounced – rhymes with "oink") is an open-source middleware system for volunteer computing (a type of distributed computing). Developed originally to support SETI@home, it beca ...
*
List of volunteer computing projects
This is a comprehensive list of volunteer computing projects; a type of distributed computing where volunteers donate computing time to specific causes. The donated computing power comes from idle CPUs and GPUs in personal computers, video game co ...
*
PrimeGrid
PrimeGrid is a volunteer computing project that searches for very large (up to world-record size) prime numbers whilst also aiming to solve long-standing mathematical conjectures. It uses the Berkeley Open Infrastructure for Network Computing ...