Proth primes: Definition and Status

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.

Primes k.2n+1
Range of k Ranges of n Completed to
3-5 8,000,000-10,000,000 8,000,000
7-15 4,500,000-7,000,000 4,500,000
17-99 3,000,000-3,500,000 3,000,000
101-199 2,000,000-2,500,000 2,000,000
201-299 2,000,000-2,500,000 2,000,000
301-399 2,000,000-2,500,000 2,000,000
401-499 2,000,000-2,500,000 2,000,000
501-599 1,500,000-2,000,000 1,500,000
601-699 1,500,000-2,000,000 1,500,000
701-799 1,500,000-2,000,000 1,500,000
801-899 1,500,000-2,000,000 1,500,000
901-999 1,500,000-2,000,000 1,500,000
1001-1099 1,500,000-2,000,000 1,500,000
1101-1199 1,500,000-2,000,000 1,500,000

If you have any questions about the Proth Search, you can e-mail Mark Rodenkirch or Ray Ballinger

Last Modified: September 16, 2013