Great Internet Mersenne Prime Search
Encyclopedia
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.
The project has found a total of thirteen Mersenne primes
, eleven of which were the largest known prime number at their respective times of discovery. The largest known prime 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. 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. 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, an algorithm
that is both specialized to testing Mersenne primes and particularly efficient on binary
computer architecture
s. 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.
computers.
The name for the project was coined by Luther Welsh, one of its earlier searchers and the 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.
of approximately 68 teraflops
.
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
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
.
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.
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.
Computer software
Computer software, or just software, is a collection of computer programs and related data that provide the instructions for telling a computer what to do and how to do it....
to search for Mersenne prime numbers
Mersenne prime
In mathematics, a Mersenne number, named after Marin Mersenne , is a positive integer that is one less than a power of two: M_p=2^p-1.\,...
. The project was founded by George Woltman
George Woltman
George Woltman is the founder of the Great Internet Mersenne Prime Search , a distributed computing project researching Mersenne prime numbers using his software Prime95 and MPrime. He graduated from the Massachusetts Institute of Technology with degrees in computer science. He is presently...
, who also wrote the software Prime95
Prime95
Prime95 is the name of the Microsoft Windows-based software application written by George Woltman that is used by GIMPS, a distributed computing project dedicated to finding new Mersenne prime numbers....
and MPrime for the project. Scott Kurowski
Scott Kurowski
Scott Kurowski is an entrepreneurial software technologist and inventor. In 1997 he founded Entropia, a venture capital funded company selling grid computing software. In 2000, he built a grid computing system searching for HIV protease inhibitors for The Scripps Research Institute...
wrote the Internet PrimeNet Server
Server (computing)
In the context of client-server architecture, a server is a computer program running to serve the requests of other programs, the "clients". Thus, the "server" performs some computational task on behalf of "clients"...
that supports the research to demonstrate Entropia
Entropia, Inc. (company)
Entropia, Inc. was a company founded in 1997 that sold distributed computing software for CPU scavenging.Their product's server infrastructure was based on Microsoft Windows....
-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
Distributed computing
Distributed computing is a field of computer science that studies distributed systems. A distributed system consists of multiple autonomous computers that communicate through a computer network. The computers interact with each other in order to achieve a common goal...
projects over the Internet for research purposes.
The project has found a total of thirteen Mersenne primes
Prime number
A prime number 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 called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
, eleven of which were the largest known prime number at their respective times of discovery. The largest known prime is 243,112,609 − 1
2^43112609 − 1
243112609 − 1 is the largest known Mersenne prime and the largest known prime number with 12,978,189 digits. Its discovery resulted from the Great Internet Mersenne Prime Search , and won its discoverers $100,000 and a Cooperative Computing Award from the Electronic Frontier...
(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
University of California, Los Angeles
The University of California, Los Angeles is a public research university located in the Westwood neighborhood of Los Angeles, California, USA. It was founded in 1919 as the "Southern Branch" of the University of California and is the second oldest of the ten campuses...
Mathematics Department. This prime allowed GIMPS to win the $100,000 prize from Electronic Frontier Foundation
Electronic Frontier Foundation
The Electronic Frontier Foundation is an international non-profit digital rights advocacy and legal organization based in the United States...
for discovering a prime with more than 10 million decimal digits. 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
Edouard Lucas
François Édouard Anatole Lucas was a French mathematician. Lucas is known for his study of the Fibonacci sequence. The related Lucas sequences and Lucas numbers are named after him.-Biography:...
and Derrick Henry Lehmer
Derrick Henry Lehmer
Derrick Henry "Dick" Lehmer was an American mathematician who refined Édouard Lucas' work in the 1930s and devised the Lucas–Lehmer test for Mersenne primes...
's primality
Primality test
A primality test is an algorithm for determining whether an input number is prime. Amongst other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating whether the input number is prime or not...
test, an algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
that is both specialized to testing Mersenne primes and particularly efficient on binary
Binary numeral system
The binary numeral system, or base-2 number system, represents numeric values using two symbols, 0 and 1. More specifically, the usual base-2 system is a positional notation with a radix of 2...
computer architecture
Computer architecture
In computer science and engineering, computer architecture is the practical art of selecting and interconnecting hardware components to create computers that meet functional, performance and cost goals and the formal modelling of those systems....
s. They also have a less expensive trial division
Trial division
Trial division is the most laborious but easiest to understand of the integer factorization algorithms. Its ease of implementation makes it a viable integer factorization option for devices with little available memory, such as graphing calculators....
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
John Pollard (mathematician)
John M. Pollard is a British mathematician who has invented algorithms for the factorization of large numbers and for the calculation of discrete logarithms....
p − 1 algorithm is also used to search for larger factors.
History
The project began in early January 1996, with a program that ran on i386Intel 80386
The Intel 80386, also known as the i386, or just 386, was a 32-bit microprocessor introduced by Intel in 1985. The first versions had 275,000 transistors and were used as the central processing unit of many workstations and high-end personal computers of the time...
computers.
The name for the project was coined by Luther Welsh, one of its earlier searchers and the 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 throughputThroughput
In communication networks, such as Ethernet or packet radio, throughput or network throughput is the average rate of successful message delivery over a communication channel. This data may be delivered over a physical or logical link, or pass through a certain network node...
of approximately 68 teraflops
FLOPS
In computing, FLOPS is a measure of a computer's performance, especially in fields of scientific calculations that make heavy use of floating-point calculations, similar to the older, simpler, instructions per second...
.
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
Source code
In computer science, source code is text written using the format and syntax of the programming language that it is being written in. Such a language is specially designed to facilitate the work of computer programmers, who specify the actions to be performed by a computer mostly by writing source...
is publicly available, technically it is not free software
Free software
Free software, software libre or libre software is software that can be used, studied, and modified without restriction, and which can be copied and redistributed in modified or unmodified form either without restriction, or with restrictions that only ensure that further recipients can also do...
, since it has a restriction that users must abide by the project's distribution terms
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
Electronic Frontier Foundation
The Electronic Frontier Foundation is an international non-profit digital rights advocacy and legal organization based in the United States...
.
Primes found
All Mersenne primes are in the form Mq, where q is the (prime) exponent. The prime number itself is so the smallest prime number in this table isMn 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 Pentium The original Pentium microprocessor was introduced on March 22, 1993. Its microarchitecture, deemed P5, was Intel's fifth-generation and first superscalar x86 microarchitecture. As a direct extension of the 80486 architecture, it included dual integer pipelines, a faster FPU, wider data bus,... (90 MHz Hertz The hertz is the SI unit of frequency defined as the number of cycles per second of a periodic phenomenon. One of its most common uses is the description of the sine wave, particularly those used in radio and audio applications.... ) |
| 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 Advanced Micro Devices Advanced Micro Devices, Inc. or AMD is an American multinational semiconductor company based in Sunnyvale, California, that develops computer processors and related technologies for commercial and consumer markets... 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 Pentium 4 Pentium 4 was a line of single-core desktop and laptop central processing units , introduced by Intel on November 20, 2000 and shipped through August 8, 2008. They had a 7th-generation x86 microarchitecture, called NetBurst, which was the company's first all-new design since the introduction of the... (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 Overclocking Overclocking is the process of operating a computer component at a higher clock rate than it was designed for or was specified by the manufacturer, but some manufacturers purposely underclock their components to improve battery life. Many people just overclock or 'rightclock' their hardware to... 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
Word processor
A word processor is a computer application used for the production of any sort of printable material....
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
- List of distributed computing projects
- Distributed computingDistributed computingDistributed computing is a field of computer science that studies distributed systems. A distributed system consists of multiple autonomous computers that communicate through a computer network. The computers interact with each other in order to achieve a common goal...
- PrimeGridPrimeGridPrimeGrid is a distributed computing project for searching for prime numbers of world-record size. It makes use of the Berkeley Open Infrastructure for Network Computing platform...
- Berkeley Open Infrastructure for Network ComputingBerkeley Open Infrastructure for Network ComputingThe Berkeley Open Infrastructure for Network Computing is an open source middleware system for volunteer and grid computing. It was originally developed to support the SETI@home project before it became useful as a platform for other distributed applications in areas as diverse as mathematics,...