**Proth's Theorem** (1878): Let *N = k*.2^{n}*+*1
with 2^{n}* > 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

- NewPGen or srsieve to sieve a range of n for a given k
- PRP or LLR to test for primality on x86 CPUs
- phrot to test for primality on any CPU
- PFGW to test for Fermat and Generalized Fermat divisibiilty (using the -gx switch)

Primes of the form *k*.2^{n}+1 are
interesting as possible factors of **Fermat numbers** *F*_{m}
= 2^{r} + 1, where *r* = 2^{m}
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*.2^{n}+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.2^{n}+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.2^{n}+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

URL: http://www.prothsearch.net/status.htmlLast Modified: September 16, 2013