Great Internet Mersenne Prime Search
The Great Internet Mersenne Prime Search ( GIMPS ) is a collaborative project for computer-aided search for Mersenne primes. The project was founded by George Woltman, who also wrote the software Prime95 and MPrime for the project. Scott Kurowski programmed the Internet PrimeNet server. GIMPS is registered as Mersenne Research, Inc.. It was the first extensive use of distributed computing over the Internet for research purposes.
- 2.1 primes found
- 3.1 The Lucas- Lehmer test
The GIMPS research project
GIMPS offers worldwide participation in a project for distributed computing to find Mersenne primes. The necessary software programmed George Woltman from 1996, can be downloaded from the GIMPS download website. As Prime95 and MPrime this software is available for installation on various Intel or AMD microprocessor -based operating systems, including Windows 64 -bit and 32 -bit, Mac OS X, Linux 64 -bit and 32 -bit, FreeBSD and PC - BSD 64 -bit and 32 -bit. For other computer platforms and programs mlucas Glucas are available. After installing the respective Prime95 software version on a computer communicates this on the fly with the Internet PrimeNet server by Scott Kurowski to register, etc. ( interim) results to store eliminated Mersenne prime candidates and manage gimps user data. The GIMPS PrimeNet server is run together with the loosely coupled computers that Prime95 or MPrime, a grid computing network for distributed computing in which a virtual supercomputer for compute-intensive scientific and mathematical search for Mersenne primes produced.
The GIMPS supercomputer achieved on 6 April 2000 the price of the Electronic Frontier Foundation (EFF) of U.S. $ 50,000 for the first time finding a prime number with more than one million decimal digits. It is the 38th Mersenne prime M6.972.593, which has 2,098,960 points and on 1 June 1999 with a 350 MHz Pentium II IBM Aptiva PC was found. The award went to parts of gimps and Nayan Hajratwala from Plymouth, Michigan. Edson Smith found the 47th known Mersenne prime M42.643.801 which registered by the GIMPS project on 12 April 2009 and was released on June 12, 2009. Edson Smith, George Woltman, Scott Kurowski, including the EFF received the award for the first time finding a prime with more than ten million digits of U.S. $ 100,000, he went on 14 October 2009 to the following parts of gimps and the Mathematics Department of the University of California in Los Angeles ( UCLA).
With U.S. $ 150,000 for finding the first prime number with more than 100 million decimal digits ( 100 million ) and U.S. $ 250,000 for the first finding a prime with more than 1 billion decimal digits ( 1,000,000,000 ) are two other prizes, the so-called Cooperative computing Awards EFF, advertised. The GIMPS supercomputer active in this program, in Prime95 or the MPrime software and in the management of his own account on the PrimeNet server to control the Prime95 or the MPrime software, finding zifferigen Mersenne primes can be adjusted as 100 million.
Status
Beginning in February 2013 made an average throughput of approximately 130.546 TFLOP / s ( teraflops per second) gimps. In March 2012, GIMPS had an average throughput of approximately 86.107 TFLOP / s, which gimps theoretically brought the place under the 153 most powerful computers in the world. In October 2010, GIMPS PrimeNet made around 50 TFLOP / s, mid-2008, there were about 30 TFLOP / s, in mid-2006 about 20 TFLOP / s and early 2004 about 14 TFLOP / s
History
The GIMPS project began in January 1996 with a program that ran on i386 computers. The first time was tested exponent M859.433. The name for the project was found by Luther Welsh, one of the first participants and discoverer of the 29th Mersenne prime. Within a few months in 1996, several dozen people had joined, over a thousand at the end of the first year. Joel Armengaud, a participant, the primality of M1.398.269 discovered on 13 November 1996.
Found primes
See: Mersenne prime
To date ( February 2013 ) the project has a total of 14 Mersenne primes have been found. Currently, the largest prime number 257,885,161 - 1 (or short M57, 885.161 ). It was discovered on January 25, 2013 Curtis Cooper at the University of Central Missouri.
All Mersenne primes are powers of 2, minus 1, about 23-1 = 7, while about the Mersenne number 24-1 = 15 is not prime. Mersenne primes have the form Mq, where q is the exponent. The prime number itself is 2q - 1 Thus, the smallest prime number in the table below 21,398,269 - 1
Mn is the rank of the Mersenne prime according to their exponents. M43 is the largest Mersenne prime for her rank was proved, since all minor candidates were tested in duplicate.
Whenever a possible prime number to the server is reported, a verification (second test ) is performed to avoid false alarms before their promulgation: 2003, for example, an incorrect as 40th Mersenne prime was reported.
The software
→ Main article: MPrime
The project used to search for Mersenne prime numbers predominantly the computer-based Lucas- Lehmer test (LL- test) by Édouard Lucas and Derrick Henry Lehmer, an algorithm that specializes in testing Mersenne primes and particularly efficient in binary computer systems.
Before the actual LL test is done with a short phase sample contained divisions to small factors. Computerized sample divisions take compared to the LL tests is much shorter, only days instead of weeks. This can be sorted out quickly and efficiently Mersenne prime candidate if can be found for these small factors. This efficient elimination of candidates is regularly met for a large number of candidates, it is about every third candidate divisible by three, one in five by five, etc. John M. Pollard P - 1 algorithm is in the search for larger factors contained Mersenne prime candidates used.
Although the GIMPS source code is freely available, the software is not regarded as free software, because users must bind to the project conditions, the gimps End User License Agreement ( EULA) and gimps Terms and Conditions of Use (TCU ), this is especially true in the search for Mersenne primes.
The Lucas- Lehmer test
→ Main article: Lucas- Lehmer test
This test is a specially tailored to Mersenne prime numbers test on the work of Édouard Lucas from the period 1870 - 1876 is based and was supplemented in 1930 by Derrick Lehmer.
It works as follows: