PrimeGrid

PrimeGrid is a volunteer distributed computing project which searches for very large (up to near-world-record size) prime numbers whilst also aiming to solve long-standing mathematical conjectures. It uses the Berkeley Open Infrastructure for Network Computing (BOINC) platform. PrimeGrid offers a number of subprojects for prime-number sieving and discovery. Some of these are available through the BOINC client, others through the PRPNet client. Some of the work is manual, i.e. it requires manually starting work units and uploading results. Different subprojects may run on different operating systems, and may have executables for CPUs, GPUs, or both; while running the Lucas–Lehmer–Riesel test, CPUs with Advanced Vector Extensions and Fused Multiply-Add instruction sets will yield the fastest results for non-GPU accelerated workloads.

PrimeGrid
Original author(s)Rytis Slatkevičius
Initial releaseJune 12, 2005 (2005-06-12)[1]
Development statusActive
Project goal(s)Finding prime numbers of various types
Software usedBOINC, PRPNet, Genefer, LLR, PFGW
FundingCorporate sponsorship, crowdfunding[2][3]
Average performance1,585 TFLOPS[4]
Active users3,381 (June 2020)[4]
Total users350,614[4]
Active hosts11,466 (June 2020)[4]
Total hosts41,810[4]
Websiteprimegrid.com

PrimeGrid awards badges to users in recognition of achieving certain defined levels of credit for work done. The badges are of no intrinsic value but are valued by many as a sign of achievement. The issuing of badges should also benefit PrimeGrid by evening out the participation in the less popular sub projects. The easiest of the badges can often be obtained in less than a day by a single computer, whereas the most challenging badges will require far more time and computing power.

History

PrimeGrid started in June 2005[1] under the name Message@home and tried to decipher text fragments hashed with MD5. Message@home was a test to port the BOINC scheduler to Perl to obtain greater portability. After a while the project attempted the RSA factoring challenge trying to factor RSA-640. After RSA-640 was factored by an outside team in November 2005, the project moved on to RSA-768. With the chance to succeed too small, it discarded the RSA challenges, was renamed to PrimeGrid, and started generating a list of the first prime numbers. At 210,000,000,000[5] the primegen subproject was stopped.

In June 2006, dialog started with Riesel Sieve to bring their project to the BOINC community. PrimeGrid provided PerlBOINC support and Riesel Sieve was successful in implementing their sieve as well as a prime finding (LLR) application. With collaboration from Riesel Sieve, PrimeGrid was able to implement the LLR application in partnership with another prime finding project, Twin Prime Search (TPS). In November 2006, the TPS LLR application was officially released at PrimeGrid. Less than two months later, January 2007, the record twin was found by the original manual project. TPS has since been completed, while the search for Sophie Germain primes continues.

In the summer of 2007, the Cullen and Woodall prime searches were launched. In the Fall, more prime searches were added through partnerships with the Prime Sierpinski Problem and 3*2^n-1 Search projects. Additionally, two sieves were added: the Prime Sierpinski Problem combined sieve which includes supporting the Seventeen or Bust sieve and the combined Cullen/Woodall sieve. In the fall of the same year, PrimeGrid migrated its systems from PerlBOINC to standard BOINC software.

Since September 2008, PrimeGrid is also running a Proth prime sieving subproject.[6]

In January 2010 the subproject Seventeen or Bust (for solving the Sierpinski problem) was added.[7] The calculations for the Riesel problem followed in March 2010.

Projects

As of July 2019, PrimeGrid is working on or has worked on the following projects:

Project Active sieve project? Active LLR project? Start End Best result
321 Prime Search (primes of the form 3×2n±1) Yes Yes 30 June 2008 Ongoing 3×211895718-1, largest prime found in the 321 Prime Search project[8]
AP26 Search (Arithmetic progression of 26 primes) N/A N/A 27 December 2008 12 April 2010 43142746595714191 + 23681770×23#×n, n = 0...25 (AP26)[9]
AP27 Search (Arithmetic progression of 27 primes) N/A N/A 20 September 2016 Ongoing 224584605939537911+81292139*23#×n, n = 0...26 (AP27)[10]
Generalized Fermat Prime Search[11][12]
(active: n = 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304 inactive: n = 8192, 16384)		 Yes (manual sieving) N/A January 2012 Ongoing 10590941048576+1, largest known Generalized Fermat prime[13]
Cullen Prime Search No Yes August 2007 Ongoing 6679881×26679881+1, largest known Cullen prime[14]
Message7 No N/A 12 June 2005 August 2005 PerlBOINC testing successful
Prime Sierpinski Problem No Yes 10 July 2008 Ongoing 168451×219375200+1[15]
Extended Sierpinski Problem No Yes 7 June 2014 Ongoing 193997×211452891+1, largest prime found in the Extended Sierpinski Problem[16]
PrimeGen No N/A March 2006 February 2008 N/A
Proth Prime Search Yes Yes 29 February 2008 Ongoing 7×25775996+1[17]
Riesel Problem No Yes March 2010 Ongoing 273809×28932416-1, largest prime found in the Riesel problem[18]
RSA-640 No N/A August 2005 November 2005 N/A
RSA-768 No N/A November 2005 March 2006 N/A
Seventeen or Bust No Yes 31 January 2010 Ongoing 10223 ×2 31172165+1
Sierpinski/Riesel Base 5 Problem No Yes 14 June 2013 Ongoing 322498×52800819−1, largest prime found in the Sierpinski/Riesel Base 5 Problem[19]
Sophie Germain Prime Search No Yes 16 August 2009 Ongoing 2618163402417×21290000-1 (2p-1 = 2618163402417×21290001-1), the world record Sophie Germain prime;[20] and 2996863034895*21290000±1, the world record twin primes[21]
Twin prime Search No N/A 26 November 2006 25 July 2009 65516468355×2333333±1[22]
Woodall Prime Search No Yes July 2007 Ongoing 17016602×217016602−1, largest known Woodall prime[23]
Generalized Cullen/Woodall Prime Search No Yes 22 October 2016 Ongoing 1806676×411806676+1, largest known generalized Cullen prime[24]

321 Prime Search is a continuation of Paul Underwood's 321 Search which looked for primes of the form 3 · 2n − 1. PrimeGrid added the +1 form and continues the search up to n = 25M.

Primes known for 3 · 2n + 1 occur at the following n:

1, 2, 5, 6, 8, 12, 18, 30, 36, 41, 66, 189, 201, 209, 276, 353, 408, 438, 534, 2208, 2816, 3168, 3189, 3912, 20909, 34350, 42294, 42665, 44685, 48150, 54792, 55182, 59973, 80190, 157169, 213321, 303093, 362765, 382449, 709968, 801978, 916773, 1832496, 2145353, 2291610, 2478785, 5082306, 7033641, 10829346 (sequence A002253 in the OEIS)

Primes known for 3 · 2n − 1 occur at the following n:

0, 1, 2, 3, 4, 6, 7, 11, 18, 34, 38, 43, 55, 64, 76, 94, 103, 143, 206, 216, 306, 324, 391, 458, 470, 827, 1274, 3276, 4204, 5134, 7559, 12676, 14898, 18123, 18819, 25690, 26459, 41628, 51387, 71783, 80330, 85687, 88171, 97063, 123630, 155930, 164987, 234760, 414840, 584995, 702038, 727699, 992700, 1201046, 1232255, 2312734, 3136255, 4235414, 6090515, 11484018, 11731850, 11895718, (sequence A002235 in the OEIS)

PRPNet projects
Project Active? Start End Best result
27 Prime Search Yes N/A Ongoing 27×25213635+1, largest known Sierpinski prime for b = 2 and k = 27
27×24583717−1, largest known Riesel prime for b = 2 and k = 27[25]
121 Prime Search Yes N/A Ongoing 121×24553899−1, largest known Riesel prime for b = 2 and k = 121[26]
Extended Sierpinski problem No N/A 2014 90527×29162167+1[27]
Factorial Prime Search Yes N/A Ongoing 147855! - 1, 2nd largest known factorial prime
Dual Sierpinski problem (Five or Bust) No N/A All were done (all PRPs were found) 29092392 + 40291
Generalized Cullen/Woodall Prime Search No N/A 2017[28] 427194×113427194 + 1, largest known GCW prime[29]
Mega Prime Search No N/A 2014 87×23496188 + 1, largest known prime for k = 87
Primorial Prime Search Yes 2008[30] Ongoing 1098133#−1, largest known primorial prime[31]
Proth Prime Search No 2008 2012[32] 10223×231172165+1, largest known Proth prime
Sierpinski Riesel Base 5 No 2009[33] 2013[34] 180062×52249192−1
Wieferich Prime Search No 2012[35] 2017[36] 82687771042557349, closest near-miss above 3×1015
Wall-Sun-Sun Prime Search No 2012[35] 2017[36] 6336823451747417, closest near-miss above 9.7×1014

Accomplishments

AP26

One of PrimeGrid projects was AP26 Search which searched for a record 26 primes in arithmetic progression. The search was successful in April 2010 with the finding of the first known AP26:

43142746595714191 + 23681770 · 23# · n is prime for n = 0, ..., 25.[37]
23# = 2·3·5·7·11·13·17·19·23 = 223092870, or 23 primorial, is the product of all primes up to 23.


AP27

Next target of the project was AP27 Search which searched for a record 27 primes in arithmetic progression. The search was successful in September 2019 with the finding of the first known AP27:

224584605939537911 + 81292139 · 23# · n is prime for n = 0, ..., 26.[38]
23# = 2·3·5·7·11·13·17·19·23 = 223092870, or 23 primorial, is the product of all primes up to 23.

PrimeGrid is also running a search for Cullen prime numbers, yielding the two largest known Cullen primes. The first one being the 14th largest known prime at the time of discovery, and the second one was PrimeGrid's largest prime found 6679881 · 26679881+1 at over 2 million digits.[39]

On 31 October 2018, PrimeGrid discovered the largest known Generalized Fermat prime to date, 10590941048576+1. This prime is 6,317,602 digits long and is only the second Generalized Fermat prime found for n = 20. It ranks as the 13th largest known prime overall.[40]

Riesel Problem

As of 13 December 2017, PrimeGrid has eliminated 15 values of k from the Riesel problem[41] and is continuing the search to eliminate the 49 remaining numbers.

Primegrid worked with the Twin Prime Search to search for a record-sized twin prime at approximately 58,700 digits. The new world's largest known twin prime 2003663613 × 2195000 ± 1 was eventually discovered on January 15, 2007 (sieved by Twin Prime Search and tested by PrimeGrid). The search continued for another record twin prime at just above 100,000 digits. It was completed in August 2009 when Primegrid found 65516468355 × 2333333 ± 1. Continued testing for twin primes in conjunction with the search for a Sophie Germain prime yielded a new record twin prime on September 2016 upon finding the number 2996863034895 × 21290000 ± 1 composed of 388,342 digits.

As of 22 April 2010, the project has discovered the three largest Woodall primes known to date.[42] The largest of these, 3752948 × 23752948 − 1, is the first mega prime discovered by the project and is 1129757 digits long. It was discovered on December 21, 2007 by Matthew J Thompson using the LLR program.[43] The search continues for an even bigger Woodall prime. PrimeGrid also found the largest known generalized Woodall prime,[44] 563528 × 13563528 − 1.

Media coverage

PrimeGrid's author Rytis Slatkevičius has been featured as a young entrepreneur in The Economist.[45]

PrimeGrid has also been featured in an article by Francois Grey in the CERN Courier and a talk about citizen cyberscience in TEDx Warwick conference.[46][47]

In the first Citizen Cyberscience Summit, Rytis Slatkevičius gave a talk as a founder of PrimeGrid, named Finding primes: from digits to digital technology,[48] relating mathematics and volunteering and featuring the history of the project.[49]

gollark: That would be with hyper-optimized concurrent code.
gollark: None of that looks particularly expensive, weird.
gollark: I... don't think that's a thing, what is your code doing?
gollark: What?
gollark: A database is probably unnecessary.

References
  1. "PrimeGrid's Challenge Series - 2008 Final Standings". PrimeGrid. Retrieved 2011-09-19.
  2. "PrimeGrid's new server (again)". PrimeGrid. Retrieved 2016-10-09.
  3. https://www.primegrid.com/donations.php
  4. "PrimeGrid - Detailed Stats". BOINCstats. Retrieved 14 June 2020.
  5. "Prime Lists". PrimeGrid. Archived from the original on 2010-05-30. Retrieved 2011-09-19.
  6. John. "PrimeGrid forum: PPS Sieve". PrimeGrid. Retrieved 2011-09-19.
  7. John. "PrimeGrid forum: Seventeen or Bust and the Sierpinski Problem". PrimeGrid. Retrieved 2011-09-19.
  8. "PrimeGrid's 321 Prime Search" (PDF). PrimeGrid. Retrieved 2019-07-28.
  9. "PrimeGrid's AP26 Search" (PDF). PrimeGrid. Retrieved 2011-09-19.
  10. "PrimeGrid's AP26 Search" (PDF). PrimeGrid. Retrieved 2019-10-23.
  11. "Genefer statistics". PrimeGrid. Retrieved 2015-11-04.
  12. "GFN Prime Search Status and History". PrimeGrid. Retrieved 2017-03-04.
  13. "PrimeGrid's Generalized Fermat Prime Search" (PDF). PrimeGrid. Retrieved 2019-07-28.
  14. "PrimeGrid's Cullen Prime Search" (PDF). PrimeGrid. Archived from the original (PDF) on 2011-09-26. Retrieved 2011-09-19.
  15. "PrimeGrid's Prime Sierpinski Problem" (PDF). PrimeGrid. Retrieved 2019-07-28.
  16. "PrimeGrid's Extended Sierpinski Problem" (PDF). PrimeGrid. Retrieved 2019-07-28.
  17. "PrimeGrid's Proth Prime Search" (PDF). PrimeGrid. Retrieved 10 March 2016.
  18. "PrimeGrid's The Riesel Problem" (PDF). PrimeGrid. Retrieved 2019-07-28.
  19. "PrimeGrid's Sierpinski/Riesel Base 5 Problem" (PDF). PrimeGrid. Retrieved 2019-07-28.
  20. "World Record Sophie Germain prime" (PDF). PrimeGrid. Retrieved 2019-07-28.
  21. "World Record Sophie Germain prime" (PDF). PrimeGrid. Retrieved 2019-07-28.
  22. "PrimeGrid's Twin Prime Search" (PDF). PrimeGrid. Archived from the original (PDF) on 2011-09-26. Retrieved 2011-09-19.
  23. "PrimeGrid's Woodall Prime Search" (PDF). PrimeGrid. Retrieved 2019-07-28.
  24. "PrimeGrid's Generalized Cullen/Woodall Prime Search" (PDF). PrimeGrid. Retrieved 2019-07-28.
  25. "PrimeGrid's 27121 Prime Search" (PDF). PrimeGrid. Retrieved 2015-02-01.
  26. "PrimeGrid's 27121 Prime Search" (PDF). PrimeGrid. Retrieved 2013-06-30.
  27. "The Prime Database: 211195*2^3224974+1". The Prime Database. Retrieved 2014-03-09.
  28. JimB. "PRPNet GCW Port 12004 being closed soon". PrimeGrid. Retrieved 10 November 2017.
  29. "PrimeGridʼs Generalized Cullen/Woodall Prime Search" (PDF). PrimeGrid. Retrieved 2014-03-09.
  30. "PrimeGrid news archive". PrimeGrid. Retrieved 2014-04-23.
  31. "PrimeGridʼs Primorial Prime Search" (PDF). PrimeGrid. Retrieved 2014-03-09.
  32. "PRPNet PPSELow on prpnet2.mine.nu will be closed". PrimeGrid. Retrieved 2013-07-13.
  33. "PRNet Discussion( Old )". PrimeGrid. Retrieved 2013-07-01.
  34. "SR5 Has moved to BOINC, PRPNet port to close soon". PrimeGrid. Retrieved 2013-07-01.
  35. "Welcome to a week of Wieferich and Wall-Sun-Sun". PrimeGrid. Retrieved 2013-07-03.
  36. JimB. "All PRPNet ports are set to No New Work". PrimeGrid Forum. PrimeGrid. Retrieved 10 November 2017.
  37. John. "AP26 Found!!!". PrimeGrid. Retrieved 2011-09-19.
  38. Michael Goetz. "AP27 Found!!!". PrimeGrid. Retrieved 2020-07-09.
  39. "The Top Twenty: Cullen primes". University of Tennessee Martin. Retrieved 2011-09-19.
  40. "919444^1048576+1 is prime!". PrimeGrid. Retrieved 2018-11-04.
  41. "PrimeGridʼs The Riesel Problem" (PDF). PrimeGrid. Retrieved 2017-12-22.
  42. "The Top Twenty: Woodall Primes". University of Tennessee Martin. Retrieved 2011-09-19.
  43. kp1139 (2007-12-28). "Cullen/Woodall prime search: First Woodall Mega Prime". PrimeGrid. Retrieved 2011-09-19.
  44. "The Top Twenty: Generalized Woodall". University of Tennessee Martin. Retrieved 2011-09-19.
  45. "Spreading the load". The Economist. 2007-12-06. Retrieved 2010-02-08.
  46. Francois Grey (2009-04-29). "Viewpoint: The Age of Citizen Cyberscience". CERN Courier. Retrieved 2010-04-26.
  47. Francois Grey (2009-03-26). "Citizen Cyberscience" (Podcast). Retrieved 2010-04-26.
  48. Rytis Slatkevičius (2010-09-02), Finding primes: from digits to digital technology, archived from the original on 2010-09-15, retrieved 2010-12-03
  49. Rytis Slatkevičius (2010-08-13), Giant Prime Numbers, retrieved 2010-12-03
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.