About the Proth Prime Search
The Proth Prime Search is done in collaboration with the Proth Search project. This search looks for primes in the form of k*2^n+1. With the condition 2^n > k, these are often called Proth primes. This project also has the added bonus of possibly finding factors of "classical" Fermat numbers or Generalized Fermat numbers. As this requires PrimeFormGW (PFGW) (a primality-testing program), once PrimeGrid finds a prime, it is then tested on PrimeGrid's servers for divisibility.
Our initial goal was to double check all previous work up to n=500K for odd k<1200 and to fill in any gaps that were missed. We have accomplished that now and have increased it to n=800K. PG LLRNet searched up to n=200,000 and found several missed primes in previously searched ranges. Although primes that small did not make it into the Top 5000 Primes database, the work was still important as it may have led to new factors for "classical" Fermat numbers or Generalized Fermat numbers. While there are many GFN factors, currently there are only about 275 "classical" Fermat number factors known. Current primes found in PPS definitely make it into the Top 5000 Primes database.
Currently, PPS-Mega and PPSE are searching 1201<k<9999. PPS and PPS-Mega are both finding mega primes, but PPS-Mega is smaller and intended to be the easiest PrimeGrid project to find a mega prime in.
PPS k range being tested is more complicated. Here's our current plan:
k's max n
To put it another way, we are searching all k from 51 to 739 up to n=4M, then we will drop some k and search k from 51 to 557 up to n=4.5M.
These values were determine based on comparing the size of the numbers to the likelihood to be a GFN divisor. See this page on the PrimePages for an explanation.
The Fermat Divisor search searched 5<k<49 ahead of where PPS is currently.
For more information about "Proth" primes, please visit these links:
About Proth Search
The Proth Search project was established in 1998 by Ray Ballinger and Wilfrid Keller to coordinate a distributed effort to find Proth primes (primes of the form k*2^n+1) for k < 300. Ray was interested in finding primes while Wilfrid was interested in finding divisors of Fermat number. Since that time it has expanded to include k < 1200. Mark Rodenkirch (aka rogue) has been helping Ray keep the website up to date for the past few years.
Early in 2008, PrimeGrid and Proth Search teamed up to provide a software managed distributed effort to the search. Although it might appear that PrimeGrid is duplicating some of the Proth Search effort by re-doing some ranges, few ranges on Proth Search were ever double-checked. This has resulted in PrimeGrid finding primes that were missed by previous searchers. By the end of 2008, all new primes found by PrimeGrid were eligible for inclusion in Chris Caldwell's Prime Pages Top 5000. Sometime in 2009, over 90% of the tests handed out by PrimeGrid were numbers that have never been tested. For 2010, we hope to complete our reservation to 800K and extend it to 1M.
PrimeGrid intends to continue the search indefinitely for Proth primes.
What is LLR?
The Lucas-Lehmer-Riesel (LLR) test is a primality test for numbers of the form N = k*2^n − 1, with 2^n > k. Also, LLR is a program developed by Jean Penne that can run the LLR-tests. It includes the Proth test to perform +1 tests and PRP to test non base 2 numbers. See also:
(Edouard Lucas: 1842-1891, Derrick H. Lehmer: 1905-1991, Hans Riesel: 1929-2014).