PrimeGrid
Encyclopedia
PrimeGrid is a distributed computing
project for searching for prime number
s of world-record size. It makes use of the Berkeley Open Infrastructure for Network Computing
(BOINC) platform. , there are about 7,500 active participants (on about 16,000 host computers) from 114 countries with a total BOINC credit
of more than 112.16 billion, reporting about 1.663 petaflops
(1.663 quadrillion operations per second) of processing power.
. 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
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.
Since September 2008, PrimeGrid is also running a Proth prime sieving subproject.
In January 2010 the subproject Seventeen or Bust
was added.
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.
Primes known for 3 · 2n + 1 occur at the following n:
Primes known for 3 · 2n − 1 occur at the following n:
. The search was successful in April 2010 with the finding of the first known AP26:
and is continuing the search to eliminate the remaining numbers.
to search for a record-sized twin prime
at approximately 58700 digits. The new worlds largest known twin prime 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 .
known to date.
The largest of these, , 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.
The search continues for an even bigger Woodall prime.
PrimeGrid also found the largest known generalized Woodall prime,
.
.
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.
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,
relating mathematics and volunteering and featuring the history of the project.
Distributed computing
Distributed computing is a field of computer science that studies distributed systems. A distributed system consists of multiple autonomous computers that communicate through a computer network. The computers interact with each other in order to achieve a common goal...
project for searching for prime number
Prime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
s of world-record size. It makes use of the Berkeley Open Infrastructure for Network Computing
Berkeley Open Infrastructure for Network Computing
The Berkeley Open Infrastructure for Network Computing is an open source middleware system for volunteer and grid computing. It was originally developed to support the SETI@home project before it became useful as a platform for other distributed applications in areas as diverse as mathematics,...
(BOINC) platform. , there are about 7,500 active participants (on about 16,000 host computers) from 114 countries with a total BOINC credit
BOINC Credit System
Within the BOINC platform for volunteer computing, the BOINC Credit System helps volunteers keep track of how much CPU time they have donated to various distributed computing projects. The credit system is designed to avoid cheating by validating results before granting credit on projects...
of more than 112.16 billion, reporting about 1.663 petaflops
FLOPS
In computing, FLOPS is a measure of a computer's performance, especially in fields of scientific calculations that make heavy use of floating-point calculations, similar to the older, simpler, instructions per second...
(1.663 quadrillion operations per second) of processing power.
History
PrimeGrid started in June 2005 under the name message@home and tried to decipher text fragments encrypted with MD5MD5
The MD5 Message-Digest Algorithm is a widely used cryptographic hash function that produces a 128-bit hash value. Specified in RFC 1321, MD5 has been employed in a wide variety of security applications, and is also commonly used to check data integrity...
. 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
RSA Factoring Challenge
The RSA Factoring Challenge was a challenge put forward by RSA Laboratories on March 18, 1991 to encourage research into computational number theory and the practical difficulty of factoring large integers and cracking RSA keys used in cryptography...
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
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.
Since September 2008, PrimeGrid is also running a Proth prime sieving subproject.
In January 2010 the subproject Seventeen or Bust
Seventeen or Bust
Seventeen or Bust is a distributed computing project started in March 2002 to solve the last seventeen cases in the Sierpinski problem.-Goals:...
was added.
The calculations for the Riesel problem followed in March 2010.
In addition, PrimeGrid is helping test for a record Sophie Germain prime
Sophie Germain prime
In number theory, a prime number p is a Sophie Germain prime if 2p + 1 is also prime. For example, 23 is a Sophie Germain prime because it is a prime and 2 × 23 + 1 = 47, and 47 is also a prime number...
and sieving
Sieve theory
Sieve theory is a set of general techniques in number theory, designed to count, or more realistically to estimate the size of, sifted sets of integers. The primordial example of a sifted set is the set of prime numbers up to some prescribed limit X. Correspondingly, the primordial example of a...
for The Sierpinski Problem.
Projects
, 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) | No | 30 June 2008 | April 22 2011 | 3×27033641+1 |
| AP26 Search (Arithmetic progression Primes in arithmetic progression In number theory, the phrase primes in arithmetic progression refers to at least three prime numbers that are consecutive terms in an arithmetic progression, for example the primes .... of 26 primes) |
N/A | 27 December 2008 | 12 April 2010 | 43142746595714191 + 23681770×23#×n, n = 0…25 (AP26) |
| Cullen Prime Search | Yes (with Woodall) | August 2007 | Ongoing | 6679881×26679881+1, largest known Cullen prime |
| 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 |
| Riesel Problem Riesel number In mathematics, a Riesel number is an odd natural number k for which the integers of the form k·2n − 1 are composite for all natural numbers n.... |
Yes | March 2010 | Ongoing | 141941×24299438-1 |
| RSA640 | No | August 2005 | November 2005 | N/A |
| RSA768 | No | November 2005 | March 2006 | N/A |
| Seventeen or Bust Seventeen or Bust Seventeen or Bust is a distributed computing project started in March 2002 to solve the last seventeen cases in the Sierpinski problem.-Goals:... |
Yes (with Prime Sierpinski Problem) | 31 January 2010 | Ongoing | N/A |
| Sophie Germain Prime Sophie Germain prime In number theory, a prime number p is a Sophie Germain prime if 2p + 1 is also prime. For example, 23 is a Sophie Germain prime because it is a prime and 2 × 23 + 1 = 47, and 47 is also a prime number... 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 |
| Woodall Prime Search | Yes (with Cullen) | July 2007 | Ongoing | 3752948×23752948−1, largest known Woodall prime |
321 Prime Search
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
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
AP26
One of PrimeGrid projects was AP26 Search which searched for a record 26 primes in arithmetic progressionPrimes in arithmetic progression
In number theory, the phrase primes in arithmetic progression refers to at least three prime numbers that are consecutive terms in an arithmetic progression, for example the primes ....
. The search was successful in April 2010 with the finding of the first known AP26:
- is prime for .
- , or 23 primorialPrimorialIn mathematics, and more particularly in number theory, primorial is a function from natural numbers to natural numbers similar to the factorial function, but rather than multiplying successive positive integers, only successive prime numbers are multiplied...
, 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 is PrimeGrid's largest prime found at over 2 million digits.Riesel Problem
PrimeGrid has eliminated 7 k from the Riesel problemRiesel number
In mathematics, a Riesel number is an odd natural number k for which the integers of the form k·2n − 1 are composite for all natural numbers n....
and is continuing the search to eliminate the remaining numbers.
Twin prime search
Primegrid then worked with the Twin Prime SearchTwin Prime Search
Twin Prime Search is a distributed computing project that looks for large twin primes. It uses the programs LLR and NewPGen . It was founded on April 13, 2006 by Michael Kwok...
to search for a record-sized twin prime
Twin prime
A twin prime is a prime number that differs from another prime number by two. Except for the pair , this is the smallest possible difference between two primes. Some examples of twin prime pairs are , , , , and...
at approximately 58700 digits. The new worlds largest known twin prime 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 .
Woodall prime search
, the project has discovered the three largest Woodall primesWoodall number
In number theory, a Woodall number is any natural number of the formfor some natural number n. The first few Woodall numbers are:Woodall numbers were first studied by Allan J. C. Cunningham and H. J. Woodall in 1917, inspired by James Cullen's earlier study of the similarly-defined Cullen numbers...
known to date.
The largest of these, , 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.
The search continues for an even bigger Woodall prime.
PrimeGrid also found the largest known generalized Woodall prime,
.
Media coverage
PrimeGrid's author Rytis Slatkevičius has been featured as a young entrepreneur in The EconomistThe Economist
The Economist is an English-language weekly news and international affairs publication owned by The Economist Newspaper Ltd. and edited in offices in the City of Westminster, London, England. Continuous publication began under founder James Wilson in September 1843...
.
PrimeGrid has also been featured in an article by Francois Grey in the CERN Courier
CERN Courier
CERN Courier is a monthly trade magazine reporting news and events related to CERN's high-energy physics community. It was established in 1959 and is published by IOP Publishing since October 1998...
and a talk about citizen cyberscience in TEDx Warwick conference.
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,
relating mathematics and volunteering and featuring the history of the project.