PrimeGrid

PrimeGrid

Original author(s)	Rytis Slatkevičius
Initial release	June 12, 2005[1]
Development status	Active
Project goal(s)	Finding prime numbers of various types
Software used	BOINC, PRPNet, Genefer, LLR, PFGW
Funding	Donations[2]
Average performance	1,218.887 TFLOPS[3]
Active users	8,382 (March 2016) [3]
Total users	90,032[3]
Active hosts	11,139[3]
Total hosts	261,690[3]
Website	primegrid.com

PrimeGrid 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 (BOINC) platform.

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^[4] 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. 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. PrimeGrid and TPS then advanced their search for even larger twin primes.

The summer of 2007 was very active as 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 2007, PrimeGrid migrated its systems from PerlBOINC to standard BOINC software.

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

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

In addition, PrimeGrid is helping test for a record Sophie Germain prime.

Projects

As of March 2016, 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×2^n±1)	No	Yes	30 June 2008	Ongoing	3×2^11895718-1, largest prime found in the 321 Prime Search project[7]
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)[8]
Generalized Fermat Prime Search[9] (active: n = 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304 inactive: n = 8192, 16384)	Yes (manual sieving)	Yes	January 2012	Ongoing	475856^524288+1, largest known Generalized Fermat prime[10]
Cullen Prime Search	No	Yes	August 2007	Ongoing	6679881×2^6679881+1, largest known Cullen prime[11]
Message7	No	N/A	12 June 2005	August 2005	PerlBOINC testing successful
Prime Sierpinski Problem	Yes	Yes	10 July 2008	Ongoing	N/A
The Extended Sierpinski Problem	Yes	Yes	7 June 2014	Ongoing	161041×2^7107964+1, largest and only prime found in the Extended Sierpinski Problem[12]
PrimeGen	No	N/A	March 2006	February 2008	N/A
Proth Prime Search	Yes	Yes	29 February 2008	Ongoing	7×2^5775996+1[13]
Riesel Problem	Yes	Yes	March 2010	Ongoing	502573×2^7181987-1, largest prime found in the Riesel problem[14]
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	Yes	Yes	31 January 2010	Ongoing	19249×2^13018586+1
Sierpinski/Riesel Base 5 Problem	No	Yes	14 June 2013	Ongoing	77072×5^2139921+1, largest prime found in the Sierpinski/Riesel Base 5 Problem[15]
Sophie Germain Prime Search	No	Yes	16 August 2009	Ongoing	2618163402417×2^1290000-1 (2p-1 = 2618163402417×2^1290001-1), the world record Sophie Germain prime[16]
Twin prime Search	No	N/A	26 November 2006	25 July 2009	65516468355×2^333333±1, largest known twin primes[17]
Woodall Prime Search	No	Yes	July 2007	Ongoing	3752948×2^3752948−1, largest known Woodall prime[18]

321 Prime Search

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

Primes known for 3 · 2ⁿ + 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 OEIS)

Primes known for 3 · 2ⁿ − 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 (sequence A002235 in OEIS)

PRPNet projects

Project	Active?	Start	End	Best result
27 Prime Search	Yes	N/A	Ongoing	27×2^4583717−1, largest known prime for k = 27[19]
121 Prime Search	Yes	N/A	Ongoing	121×2^4553899−1, largest known prime for k = 121[20]
Extended Sierpinski problem	No	N/A	2014	211195×2^3224974+1[21]
Factorial Prime Search	Yes	N/A	Ongoing	147855! - 1, 2nd largest known factorial prime
Dual Sierpinski problem (Five or Bust)	No	N/A	N/A	N/A
Generalized Cullen/Woodall Prime Search	Yes	N/A	Ongoing	427194×113^427194 + 1, largest known GCW prime[22]
Mega Prime Search	No	N/A	2014	87×2^3496188 + 1, largest known prime for k = 87
Primorial Prime Search	Yes	2008[23]	Ongoing	1098133#−1, largest known primorial prime[24]
Proth Prime Search	No	2008	2012[25]	N/A
Sierpinski Riesel Base 5	No	2009[26]	2013[27]	N/A
Wieferich Prime Search	Yes	2012[28]	Ongoing	82687771042557349, closest near-miss above 3×10^15
Wall-Sun-Sun Prime Search	Yes	2012[28]	Ongoing	6336823451747417, closest near-miss above 9.7×10^14

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.^[29]

23# = 2·3·5·7·11·13·17·19·23 = 223092870, or 23 primorial, is the product of all primes up to 23.

Cullen prime search

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 · 2^6679881+1 at over 2 million digits.^[30]

Riesel Problem

As of 9 March 2014 PrimeGrid has eliminated 14 k from the Riesel problem^[31] and is continuing the search to eliminate the 50 remaining numbers.

Twin prime search

Primegrid then worked with the Twin Prime Search to search for a record-sized twin prime at approximately 58700 digits. The new world's largest known twin prime 2003663613 × 2¹⁹⁵⁰⁰⁰ ± 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 100000 digits. It was completed in August 2009 when Primegrid found 65516468355 × 2³³³³³³ ± 1. Continued testing for twin primes in conjunction with the search for a Sophie Germain prime yielded a new record twin prime on December 25, 2011 upon finding the number 3756801695685× 2⁶⁶⁶⁶⁶⁹ ± 1 composed of 200,700 digits.

Woodall prime search

As of 22 April 2010, the project has discovered the three largest Woodall primes known to date.^[32] The largest of these, 3752948 × 2^3752948 − 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.^[33] The search continues for an even bigger Woodall prime. PrimeGrid also found the largest known generalized Woodall prime,^[34] 563528 × 13⁵⁶³⁵²⁸ − 1.

Media coverage

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

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.^[36][37]

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,^[38] relating mathematics and volunteering and featuring the history of the project.^[39]

References

1. "PrimeGrid's Challenge Series - 2008 Final Standings". PrimeGrid. Retrieved 2011-09-19.
2. "Donations to PrimeGrid". PrimeGrid. Retrieved 2013-06-17.
3. "PrimeGrid - Detailed Stats". BOINCstats. Retrieved 8 March 2016.
4. "Prime Lists". PrimeGrid. Retrieved 2011-09-19.
5. John. "PrimeGrid forum: PPS Sieve". PrimeGrid. Retrieved 2011-09-19.
6. John. "PrimeGrid forum: Seventeen or Bust and the Sierpinski Problem". PrimeGrid. Retrieved 2011-09-19.
7. "PrimeGrid Primes".
8. "PrimeGrid’s AP26 Search" (PDF). PrimeGrid. Retrieved 2011-09-19.
9. "Genefer statistics". PrimeGrid. Retrieved 2015-11-04.
10. "PrimeGrid’s Generalized Fermat Prime Search" (PDF). PrimeGrid. Retrieved 2012-08-08.
11. "PrimeGrid’s Cullen Prime Search" (PDF). PrimeGrid. Retrieved 2011-09-19.
12. "PrimeGrid’s Sierpinski/Extended Sierpinski Problem" (PDF). PrimeGrid. Retrieved 2015-02-13.
13. "PrimeGrid’s Proth Prime Search" (PDF). PrimeGrid. Retrieved 10 March 2016.
14. "PrimeGrid's The Riesel Problem" (PDF). PrimeGrid. Retrieved 2015-02-01.
15. "PrimeGrid Primes".
16. "World Record Sophie Germain prime" (PDF). PrimeGrid.
17. "PrimeGrid’s Twin Prime Search" (PDF). PrimeGrid. Retrieved 2011-09-19.
18. "PrimeGrid’s Woodall Prime Search" (PDF). PrimeGrid. Retrieved 2011-09-19.
19. "PrimeGrid's 27121 Prime Search" (PDF). PrimeGrid. Retrieved 2015-02-01.
20. "PrimeGrid's 27121 Prime Search" (PDF). PrimeGrid. Retrieved 2013-06-30.
21. "The Prime Database: 211195*2^3224974+1". The Prime Database. Retrieved 2014-03-09.
22. "PrimeGridʼs Generalized Cullen/Woodall Prime Search" (PDF). PrimeGrid. Retrieved 2014-03-09.
23. "PrimeGrid news archive". PrimeGrid. Retrieved 2014-04-23.
24. "PrimeGridʼs Primorial Prime Search" (PDF). PrimeGrid. Retrieved 2014-03-09.
25. "PRPNet PPSELow on prpnet2.mine.nu will be closed.". PrimeGrid. Retrieved 2013-07-13.
26. "PRNet Discussion( Old )". PrimeGrid. Retrieved 2013-07-01.
27. "SR5 Has moved to BOINC, PRPNet port to close soon.". PrimeGrid. Retrieved 2013-07-01.
28. "Welcome to a week of Wieferich and Wall-Sun-Sun". PrimeGrid. Retrieved 2013-07-03.
29. John. "AP26 Found!!!". PrimeGrid. Retrieved 2011-09-19.
30. "The Top Twenty: Cullen primes". University of Tennessee Martin. Retrieved 2011-09-19.
31. "PrimeGridʼs The Riesel Problem" (PDF). PrimeGrid. Retrieved 2014-03-09.
32. "The Top Twenty: Woodall Primes". University of Tennessee Martin. Retrieved 2011-09-19.
33. kp1139 (2007-12-28). "Cullen/Woodall prime search: First Woodall Mega Prime". PrimeGrid. Retrieved 2011-09-19.
34. "The Top Twenty: Generalized Woodall". University of Tennessee Martin. Retrieved 2011-09-19.
35. "Spreading the load". The Economist. 2007-12-06. Retrieved 2010-02-08.
36. Francois Grey (2009-04-29). "Viewpoint: The Age of Citizen Cyberscience". CERN Courier. Retrieved 2010-04-26.
37. Francois Grey (2009-03-26). "Citizen Cyberscience" (Podcast). Retrieved 2010-04-26.
38. Rytis Slatkevičius (2010-09-02), Finding primes: from digits to digital technology, retrieved 2010-12-03
39. Rytis Slatkevičius (2010-08-13), Giant Prime Numbers, retrieved 2010-12-03

External links

• PrimeGrid