Jump to content

PrimeGrid

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Sitonera (talk | contribs) at 10:12, 12 May 2011 (→‎Riesel Problem: New prime discovered). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

PrimeGrid
Original author(s)Rytis Slatkevičius
Initial releaseJune 12, 2005; 19 years ago (2005-06-12)[1]
PlatformCross-platform
Available inEnglish
TypeDistributed computing
Websiteprimegrid.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. As of March 2011, there are about 7,500 active participants (on about 15,700 host computers) from 114 countries with a total BOINC credit of more than 35.2 billion, reporting about 1.7 petaflops (1.7 quadrillion operations per second) of processing power.[2]

History

PrimeGrid started in June 2005[1] under the name message@home and tried to decipher text fragments encrypted 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[3] 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 some of its systems from PerlBOINC to standard BOINC software. However, many of the services still remain based on PerlBOINC.[citation needed]

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

In January 2010 the subproject Seventeen or Bust was added[5]. The calculations for the Riesel problem followed in March 2010.

In addition, PrimeGrid is helping test for a record Sophie Germain prime and sieving for The Sierpinski Problem.

Projects

As of April 2010, PrimeGrid is working on or has worked on the following projects:

Project Active sieve project? Start End Best result
321 Prime Search (primes of the form 3×2n±1) Yes (to be stopped on 22 April 2011[6]) 30 June 2008 Ongoing 3×26090515−1[7]
AP26 Search (Arithmetic progression of 26 primes) N/A 27 December 2008 12 April 2010 43142746595714191 + 23681770×23#×n, n = 0…25 (AP26)[8]
Cullen Prime Search Yes (with Woodall) August 2007 Ongoing 6679881×26679881+1, largest known Cullen prime[9]
Message7 No 12 June 2005 August 2005 PerlBOINC testing successful
Prime Sierpinski Problem Yes (with Seventeen or Bust) 10 July 2008 Ongoing N/A
PrimeGen No March 2006 February 2008
Proth Prime Search Yes 29 February 2008 Ongoing 659×2617815+1, divides F617813[10]
Riesel Problem Yes March 2010 Ongoing 65531×23629342-1
RSA640 No August 2005 November 2005 N/A
RSA768 No November 2005 March 2006 N/A
Seventeen or Bust Yes (with Prime Sierpinski Problem) 31 January 2010 Ongoing N/A
Sophie Germain Prime Search No 16 August 2009 Ongoing N/A
Twin Prime Search No 26 November 2006 25 July 2009 65516468355×2333333±1, largest known twin primes[11]
Woodall Prime Search Yes (with Cullen) July 2007 Ongoing 3752948×23752948−1, largest known Woodall prime[12]

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, 2478785, 5082306 (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 (sequence A002235 in the OEIS)

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.[13]
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 is PrimeGrid's largest prime found 6679881 · 26679881+1 at over 2 million digits[14].

Riesel Problem

As of 8 May 2011 PrimeGrid has eliminated 4 k from the Riesel problem[15] and is continuing the search to eliminate the remaining numbers.

Primegrid then worked with the Twin Prime Search to search for a record-sized twin prime at approximately 58700 digits. The new worlds 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 100000 digits. It was completed in August 2009 when Primegrid found 65516468355 × 2333333 ± 1.

As of 22 April 2010, the project has discovered the three largest Woodall primes known to date.[16] 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.[17] The search for an even bigger Woodall prime continues. PrimeGrid also found the largest known generalized Woodall prime[18], 563528 × 13563528 − 1.

Media coverage

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

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

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

References

  1. ^ a b PrimeGrid's Challenge Series - 2008 Final Standings
  2. ^ "Detailed user, host, team and country statistics with graphs for BOINC", boincstats.com, retrieved 11 March 2011
  3. ^ Download Prime Lists
  4. ^ PrimeGrid forum: PPS Sieve
  5. ^ PrimeGrid forum: Seventeen or Bust and the Sierpinski Problem
  6. ^ Sub-project "life" expectancy on PrimeGrid forums
  7. ^ http://www.primegrid.com/download/321-6090515.pdf
  8. ^ http://www.primegrid.com/download/AP26.pdf
  9. ^ http://www.primegrid.com/download/Cullen6679881.pdf
  10. ^ http://www.primegrid.com/download/PPS-F617815.pdf
  11. ^ http://www.primegrid.com/download/Twin333333.pdf
  12. ^ http://www.primegrid.com/download/Woodall3752948.pdf
  13. ^ PrimeGrid forum: First ever AP26 found
  14. ^ The Prime Pages: The Top Twenty: Cullen Primes
  15. ^ Fourth Riesel prime discovery official announcement
  16. ^ The Prime Pages: The Top Twenty: Woodall Primes
  17. ^ PrimeGrid forum: First Woodall Mega Prime
  18. ^ The Prime Pages: The Top Twenty: Generalized Woodall
  19. ^ "Spreading the load". The Economist. 6 December 2007. Retrieved 8 February 2010.
  20. ^ Francois Grey (29 April 2009). "Viewpoint: The age of citizen cyberscience". CERN Courier. Retrieved 26 April 2010.
  21. ^ Francois Grey (26 March 2009), Citizen Cyberscience, retrieved 26 April 2010
  22. ^ Rytis Slatkevičius (2 September 2010), Finding primes: from digits to digital technology, retrieved 03 December 2010 {{citation}}: Check date values in: |accessdate= (help)
  23. ^ Rytis Slatkevičius (13 August 2010), Giant Prime Numbers, retrieved 03 December 2010 {{citation}}: Check date values in: |accessdate= (help)
Retrieved from "https://en.wikipedia.org/w/index.php?title=PrimeGrid&oldid=428728968"