Proth's Theorem (1878): Let N = k.2n+1 with 2n > k. If there is an integer a such that a(N-1)/2 = -1 (mod N), then N is prime.
The test is simple, in practice the difficulty is multiplying the large numbers involved. The recommended software for the search is
Primes of the form k.2n+1 are interesting as possible factors of Fermat numbers Fm = 2r + 1, where r = 2m is itself a power of two. Presently there are more than 290 such factors known (see the factoring status), so discovering a new one is a greater achievement. Please use PFGW to test for GFN divisibility of new primes. Send new GFN factors to Wilfrid Keller
In the past, numbers k.2n+1 have been tested for primality at wide areas of k and n. You can help to extend this search further by using NewPGen and LLR. Below are links to tables of ranges of exponents n that still have to be tested for individual values of k. Each table shows which ranges of n are available for current testing, and which of them have been reserved or have already been tested for 3 < k < 1200. Ranges above this are not included at this time since...
"It appears that the probability of each prime of the form k.2n+1 dividing a Fermat number is 1/k" (Harvey Dubner & Wilfrid Keller, "Factors of generalized Fermat numbers", Mathematics of Computation, Vol. 64, Number 209, January 1995, pp. 397-405).
For reserving a range, please return to the index page. Ranges of n should be reserved in blocks of 20,000, e.g., 2,500,000-2,500,000. A contiguous row of such blocks can also be reserved, though it is suggested that a range be picked that can be completed in about a 2 month period of time. If a range is reserved for more than 6 months without a status update, you will be contacted via e-mail. If that is unsuccessful, the range will be unreserved.
Preference should be given to the lowest blocks available for a given k or even on an entire table. In any case, testing should be done so that the searcher can reliably report that the chosen range has been searched completely.
|Range of k||Ranges of n||Completed to|
If you have any questions about the Proth Search, you can e-mail Mark Rodenkirch or Ray BallingerURL: http://www.prothsearch.net/status.html