Proth prime

A Proth number is a natural number N of the form where k and n are positive integers, k is odd and. A Proth prime is a Proth number that is prime. They are named after the French mathematician François Proth. The first few Proth primes are
It is still an open question whether an infinite number of Proth primes exist. It was shown in 2022 that the reciprocal sum of Proth primes converges to a real number near 0.747392479, substantially less than the value of 1.093322456 for the reciprocal sum of Proth numbers.
The primality of Proth numbers can be tested more easily than many other numbers of similar magnitude.

Definition

A Proth number takes the form where k and n are positive integers, is odd and. A Proth prime is a Proth number that is prime. Without the condition that, all odd integers larger than 1 would be Proth numbers.

Primality testing

The primality of a Proth number can be tested with Proth's theorem, which states that a Proth number is prime if and only if there exists an integer for which
This theorem can be used as a probabilistic test of primality, by checking for many random choices of whether If this fails to hold for several random, then it is very likely that the number is composite.
This test is a Las Vegas algorithm: it never returns a false positive but can return a false negative; in other words, it never reports a composite number as "probably prime" but can report a prime number as "possibly composite".
In 2008, Sze created a deterministic algorithm that runs in at most time, where Õ is the soft-O notation. For typical searches for Proth primes, usually is either fixed or of order . In these cases algorithm runs in at most, or time for all. There is also an algorithm that runs in time.
Fermat numbers are a special case of Proth numbers, wherein. In such a scenario Pépin's test proves that only base need to be checked to deterministically verify or falsify the primality of a Fermat number.

Large primes

, the largest known Proth prime is. It is 9,383,761 digits long. It was found by Szabolcs Peter in the PrimeGrid volunteer computing project which announced it on 6 November 2016. It is also the third largest known non-Mersenne prime.
The project Seventeen or Bust, searching for Proth primes with a certain to prove that 78557 is the smallest Sierpinski number, has found 11 large Proth primes by 2007. Similar resolutions to the prime Sierpiński problem and extended Sierpiński problem have yielded several more numbers.
Since divisors of Fermat numbers are always of the form, it is customary to determine if a new Proth prime divides a Fermat number.
As of January 2025, PrimeGrid is the leading computing project for searching for Proth primes. Its main projects include:

general Proth prime search
321 Prime Search
27121 Prime Search
Cullen prime search
Sierpinski problem – searching for primes of the form where k is in this list:

k ∈

As of June 2023, the largest Proth primes discovered are:

rank	prime	digits	when	Comments	Discoverer	References
1	10223 × 2^31172165 + 1	9383761	31 Oct 2016		Szabolcs Péter
2	202705 × 2^21320516 + 1	6418121	1 Dec 2021		Pavel Atnashev
3	81 × 2^20498148 + 1	6170560	13 Jul 2023	Generalized Fermat F₂	Ryan Propper
4	7 × 2^20267500 + 1	6101127	21 Jul 2022	Divides F_20267499	Ryan Propper
5	168451 × 2^19375200 + 1	5832522	17 Sep 2017		Ben Maloney
6	7 × 2^18233956 + 1	5488969	1 Oct 2020	Divides Fermat F_18233954 and F_18233952	Ryan Propper
7	13 × 2^16828072 + 1	5065756	11 Oct 2023		Ryan Propper
8	3 × 2^16408818 + 1	4939547	28 Oct 2020	Divides F_16408814, F_16408817, and F_16408815	James Brown
9	11 × 2^15502315 + 1	4666663	8 Jan 2023	Divides F_15502313	Ryan Propper
10	37 × 2^15474010 + 1	4658143	8 Nov 2022		Ryan Propper
11	× 2^7658614 + 1	4610945	31 Jul 2020	Gaussian Mersenne norm	Ryan Propper and Serge Batalov
12	13 × 2^15294536 + 1	4604116	30 Sep 2023		Ryan Propper
13	37 × 2^14166940 + 1	4264676	24 Jun 2022		Ryan Propper
14	99739 × 2^14019102 + 1	4220176	24 Dec 2019		Brian Niegocki
15	404849 × 2^13764867 + 1	4143644	10 Mar 2021	Generalized Cullen with base 131072	Ryan Propper and Serge Batalov
16	25 × 2^13719266 + 1	4129912	21 Sep 2022	F₁	Ryan Propper
17	81 × 2^13708272 + 1	4126603	11 Oct 2022	F₂	Ryan Propper
18	81 × 2^13470584 + 1	4055052	9 Oct 2022	F₂	Ryan Propper
19	9 × 2^13334487 + 1	4014082	31 Mar 2020	Divides F_13334485, F_13334486, and F_13334484	Ryan Propper
20	19249 × 2^13018586 + 1	3918990	26 Mar 2007		Konstantin Agafonov

Proth prime of the second kind

A Proth number of the second kind is a natural number N of the form where k and n are positive integers, k is odd and. A Proth prime of the second kind is a Proth number of the second kind that is prime. The first few Proth primes of the second kind are
The largest Proth primes of the second kind can be primality testing use the Lucas–Lehmer–Riesel test.
As of January 2025, PrimeGrid is the leading computing project for searching for Proth primes of the second kind. Its main projects include:

general Proth prime of the second kind search
321 Prime Search
27121 Prime Search
Woodall prime search
Riesel problem – searching for primes of the form where k is in this list:

k ∈

Uses

Small Proth primes have been used in constructing prime ladders, sequences of prime numbers such that each term is "close" to the previous one. Such ladders have been used to empirically verify prime-related conjectures. For example, Goldbach's weak conjecture was verified in 2008 up to 8.875 × 10³⁰ using prime ladders constructed from Proth primes.
Also, Proth primes can optimize den Boer reduction between the Diffie–Hellman problem and the Discrete logarithm problem. The prime number 55 × 2²⁸⁶ + 1 has been used in this way.
As Proth primes have simple binary representations, they have also been used in fast modular reduction without the need for pre-computation, for example by Microsoft.