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 only about 250 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 < 600. 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., 500,000-520,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 ia 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.
| Primes k.2n+1 |
||
|---|---|---|
| Range of k | Ranges of n | Completed to |
| 3-7 | 1,600,000-4,300,000 | 1,600,000 |
| 9-31 | 1,300,000-3,100,000 | 1,300,000 |
| 33-99 | 500,000-1,400,000 | 500,000 |
| 101-199 | 500,000-1,100,000 | 500,000 |
| 201-299 | 500,000-800,000 | 500,000 |
| 301-399 | 300,000-800,000 | 460,000 |
| 401-499 | 500,000-800,000 | 500,000 |
| 501-599 | 300,000-800,000 | 460,000 |
| 601-699 | 200,000-800,000 | 200,000 |
| 701-799 | 200,000-800,000 | 200,000 |
| 801-899 | 200,000-800,000 | 200,000 |
| 901-999 | 200,000-800,000 | 200,000 |
| 1001-1099 | 200,000-800,000 | 200,000 |
| 1101-1199 | 200,000-800,000 | 200,000 |
If you have any questions about the Proth Search, you can e-mail Mark Rodenkirch or Ray Ballinger
URL: http://www.prothsearch.net/status.html