Great Internet Mersenne Prime Search

from Wikipedia, the free encyclopedia
logo

The Great Internet Mersenne Prime Search ( GIMPS ) is a collaborative project for the computer-aided search for Mersenne prime numbers . The project was founded by George Woltman , who also wrote the Prime95 and MPrime software for the project. Scott Kurowski programmed the Internet PrimeNet - Server . GIMPS than Mersenne Research, Inc. entered. It was the first extensive use of distributed computing over the Internet for research purposes, in which computer users made their computing time available voluntarily ( volunteer computing ).

The GIMPS research project

GIMPS offers worldwide participation in a volunteer computing project to find Mersenne prime numbers. The required software , which George Woltman programmed starting in 1996, can be downloaded from the GIMPS download website. This software is available as Prime95 and MPrime for installation on various Intel or AMD microprocessor- based operating systems, including Windows 64-bit and 32-bit, macOS , Linux 64-bit and 32-bit, FreeBSD and PC-BSD 64 -bit and 32-bit. The programs Mlucas and Glucas are available for other computer platforms. After the installation of the respective Prime95 software version on a computer it communicates during operation with the Internet PrimeNet server by Scott Kurowski to others (intermediate) to register results, eliminating Mersenne prime candidate to store and manage GIMPS user data. The GIMPS PrimeNet Server, together with the loosely coupled computers running Prime95 or MPrime, is a grid computing network for distributed computing, in which a virtual supercomputer is created for the computationally intensive scientific-mathematical search for Mersenne prime numbers.

The GIMPS supercomputer won the Electronic Frontier Foundation (EFF) award of US $ 50,000 on April 6, 2000 for finding a prime number with more than one million decimal digits for the first time . It is the 38th Mersenne prime number M 6,972,593 , which has 2,098,960 digits and was found on June 1, 1999 with a 350 MHz Pentium II IBM Aptiva PC . The award went in part to GIMPS and Nayan Hajratwala of Plymouth, Michigan . Edson Smith found the 47th known Mersenne prime M 43,112,609 , which was registered by the GIMPS project on April 12, 2009 and published on June 12, 2009. Edson Smith, George Woltman, Scott Kurowski, and others received the EFF Prize for finding a prime number with more than ten million digits of US $ 100,000 for the first time. On October 14, 2009, it went in part to GIMPS and the Mathematics Department of the University of California in Los Angeles (UCLA).

With US $ 150,000 for finding the first prime number with more than 100 million decimal digits (100,000,000) and US $ 250,000 for finding a prime number with more than 1 billion decimal digits (1,000,000,000) are two further prizes, the so-called Cooperative EFF Computing Awards , announced. The GIMPS supercomputer participates in the Prime95 or MPrime software and in the management of your own account on the PrimeNet server, to control the Prime95 or MPrime software, the search for 100 million digit Mersenne prime numbers can be set.

status

At the beginning of February 2013, GIMPS achieved an average throughput of approx. 130.546 TFLOP / s (trillion arithmetic operations per second). In March 2012, GIMPS had an average throughput of approx. 86.107 TFLOP / s, which theoretically brought GIMPS 153rd place among the most powerful computers in the world. In October 2010, GIMPS-PrimeNet performed around 50 TFLOP / s, in mid-2008 it was around 30 TFLOP / s, in mid-2006 around 20 TFLOP / s and at the beginning of 2004 around 14 TFLOP / s. In January 2017, the performance was already around 367 PFLOP / s and thus theoretically ranked 468 in the world rankings.

history

The GIMPS project began in January 1996 with a program that ran on i386 computers. The first exponent tested at that time was M 859.433 . The name for the project was found by Luther Welsh, one of the first participants and the discoverer of the 29th Mersenne prime. Several dozen people had joined in just a few months in 1996, over a thousand by the end of the first year. Joel Armengaud, a participant, discovered the primality of M 1,398,269 on November 13, 1996.

Found prime numbers

See: Mersenne prime number

To date (December 2018) the project has found a total of 17 Mersenne prime numbers. Currently the largest prime number 2 is 82,589,933  - 1 (or M 82589933 for short ). It was discovered by Patrick Laroche on December 7, 2018.

Mersenne prime numbers are powers of 2 minus 1, say 2 3 -1 = 7, while the Mersenne number 2 4 -1 = 15 is not prime. They are denoted by M q , where q is the exponent. The prime number itself is 2 q - 1 . So the smallest prime number in the table below is 2 1398269 - 1.

Mn is the rank of the Mersenne prime according to its exponent. M47 is the largest Mersenne prime for which its rank has been proven, as all smaller candidates were double-checked.

Discovery date Prime number Put Surname Explorer machine
November 13, 1996 M 1398269 420.921 M35 Joel Armengaud Pentium (90 MHz )
August 24, 1997 M 2976221 895.932 M36 Gordon Spence Pentium (100 MHz)
January 27, 1998 M 3021377 909.526 M37 Roland Clarkson Pentium (200 MHz)
June 1, 1999 M 6972593 2,098,960 M38 Nayan Hajratwala Pentium (350 MHz)
November 14, 2001 M 13466917 4,053,946 M39 Michael Cameron AMD Thunderbird (800 MHz)
November 17, 2003 M 20996011 6.320.430 M40 Michael Shafer Pentium (2 GHz)
May 15, 2004 M 24036583 7,235,733 M41 Josh Findley Pentium 4 (2.4 GHz)
February 18, 2005 M 25964951 7,816,230 M42 Martin Nowak Pentium 4 (2.4 GHz)
December 15, 2005 M 30402457 9,152,052 M43 Curtis Cooper & Steven Boone Pentium 4 (2 GHz overclocked to 3 GHz)
September 4, 2006 M 32582657 9,808,358 M44 Curtis Cooper & Steven Boone Pentium 4 (3 GHz)
August 23, 2008 M 43112609 12,978,189 M47 Hans-Michael Elvenich Intel Core 2 Duo E6600 CPU (2.4 GHz)
September 6, 2008 M 37156667 11.185.272 M45 Odd M. Strindmo Intel Core 2 Duo (2.83 GHz)
January 4, 2009 M 42643801 12,837,064 M46 Edson Smith Intel Core 2 Duo (3 GHz)
January 25, 2013 M 57885161 17,425,170 M48? Curtis Cooper Intel Core 2 Duo (3 GHz)
January 7, 2016 M 74207281 22,338,618 M49? Curtis Cooper Intel i7-4790 (3.6 GHz)
December 26, 2017 M 77232917 23.249.425 M50? Jon Pace Intel i5-6600 (3.3 GHz)
7th December 2018 M 82589933 24,862,048 M51? Patrick Laroche Intel i5-4590T (2.0 GHz)

Whenever a possible prime number is reported to the server, a verification (second test) is carried out before it is announced in order to avoid false reports: in 2003, for example, an incorrect 40th Mersenne prime number was reported.

The software

For the search for Mersenne primes, the project mainly uses the computer-based Lucas-Lehmer test (LL test) by Édouard Lucas and Derrick Henry Lehmer , an algorithm that specializes in testing Mersenne primes and is particularly efficient in binary computer systems .

Before the actual LL test, there is a short phase with trial divisions for small factors included. Compared to the LL tests, computerized trial divisions last much shorter, just days instead of weeks. This allows Mersenne prime number candidates to be sorted out quickly and efficiently if small factors can be found for them. This efficient elimination of candidates is regularly performed for a large number of candidates, for example every third candidate is divisible by three, every fifth by five, and so on. John M. Pollard's P - 1 algorithm is used in Mersenne to find larger factors Prime candidate used.

Although the GIMPS source code is freely available, the software is not considered to be free software , as users must be bound by the project terms , the GIMPS End User License Agreement ( EULA ) and the GIMPS Terms and Conditions of Use ( TCU ), this is particularly true when searching for Mersenne primes.

The Lucas-Lehmer test

This test is a prime number test specially tailored to Mersenne numbers, based on the work of Édouard Lucas from the period 1870–1876 and supplemented in 1930 by Derrick Henry Lehmer.

It works like this:

Be odd and prime. The consequence is defined by .
Then: is a prime number if and only if is divisible by .

See also

Individual evidence

  1. ↑ a b PrimeNet Statistics. Retrieved February 22, 2019 .
  2. ↑ GIMPS - Free Prime95 software downloads - PrimeNet. Retrieved February 22, 2019 .
  3. ↑ mlucas - A portable program for Lucas-Lehmer tests. Retrieved February 22, 2019 .
  4. ↑ Glucas - Yet Another FFT / Wiki / Home. Retrieved February 22, 2019 .
  5. ↑ Mersenne Prime Discovery - 2 ^ 6972593-1 is Prime! Retrieved February 22, 2019 .
  6. ^ Electronic Frontier Foundation. Retrieved February 22, 2019 .
  7. ^ Titanic Primes Raced to Win $ 100,000 Research Award. Retrieved February 22, 2019 .
  8. ↑ initially this was the 45th known Mersenne prime number; shortly afterwards, however, two smaller Mersenne primes (M 37,156,667 and M 42,643,801 ) were found.
  9. ↑ Press Release: Record 12-Million-Digit Prime Number Nets $ 100,000 Prize. October 14, 2009, accessed February 22, 2019 .
  10. ↑ EFF Cooperative Computing Awards. February 29, 2008, accessed February 22, 2019 .
  11. ↑ 332.2M - 333.9M (aka 100M digit range) - mersenneforum.org. Retrieved February 22, 2019 .
  12. ↑ PrimeNet Activity Summary Aggregate Computing Power last 30 days, actual 86.107 TFLOP / sec; Accessed February 14, 2013.
  13. ↑ PrimeNet Activity Summary Aggregate Computing Power last 30 days, actual 86.107 TFLOP / sec; Accessed April 5, 2012.
  14. ↑ TOP500 as of November 2011; according to the 'HP DL160 Cluster G6' from Hewlett-Packard - HP DL160 with 87.095 TFLOP / s (R ​​max).
  15. ↑ Top500 List - November 2016 | TOP500 supercomputer sites. In: www.top500.org. Retrieved January 7, 2017 .
  16. ↑ George Woltman: The Mersenne Newsletter, issue # 1. (txt) Great Internet Mersenne Prime Search (GIMPS), February 24, 1996, accessed June 16, 2009 .
  17. ↑ a b George Woltman: The Mersenne Newsletter, issue # 9. (txt) GIMPS, January 15, 1997, accessed June 16, 2009 .
  18. ↑ mersenneforum.org - View Single Post - Trial Factoring vs. LL testing. Retrieved February 22, 2019 .
  19. ↑ The Mersenne Newsletter, Issue # 9 . Retrieved August 25, 2009.
  20. ↑ George Woltman: The Mersenne Newsletter, issue # 3. (txt) GIMPS, April 12, 1996, accessed June 16, 2009 .
  21. ↑ George Woltman: The Mersenne Newsletter, issue # 8. (txt) GIMPS, November 23, 1996, accessed June 16, 2009 .
  22. ↑ a b c d e f g h i j k l m n o p q r s t u List of Known Mersenne Prime Numbers. Great Internet Mersenne Prime Search , accessed January 3, 2018 .
  23. ↑ a b Mersenne Prime Discovery - 2 ^ 82589933-1 is Prime! December 21, 2018, accessed December 22, 2018 .
  24. ↑ heise online: Computer in Florida finds new greatest prime number. December 22, 2018, accessed December 22, 2018 .
  25. ↑ What are Mersenne primes? How are they useful? - GIMPS FAQ Page
  26. ↑ GIMPS End User License Agreement. Mersenne Research Inc, accessed April 25, 2019 .
  27. ^ GIMPS Terms and Conditions of Use. Mersenne Research Inc, accessed April 25, 2019 .

Web links