They are named after the French mathematician François Proth.
[2] 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.
[1] The primality of Proth numbers can be tested more easily than many other numbers of similar magnitude.
A Proth number takes the form
, all odd integers larger than 1 would be Proth numbers.
for which This theorem can be used as a probabilistic test of primality, by checking for many random choices of
[citation needed] 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 (e.g. 321 Prime Search or Sierpinski Problem) or of order
In such a scenario Pépin's test proves that only base a=3 need to be checked to deterministically verify or falsify the primality of a Fermat number.
As of 2022[update], the largest known Proth prime is
[7] It was found by Szabolcs Peter in the PrimeGrid volunteer computing project which announced it on 6 November 2016.
[9] The project Seventeen or Bust, searching for Proth primes with a certain
to prove that 78557 is the smallest Sierpinski number (Sierpinski problem), 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.
, it is customary to determine if a new Proth prime divides a Fermat number.
[10] As of January 2025, PrimeGrid is the leading computing project for searching for Proth primes.
Its main projects include: k ∈ {21181, 22699, 24737, 55459, 67607, 79309, 79817, 91549, 99739, 131179, 152267, 156511, 163187, 200749, 209611, 222113, 225931, 227723, 229673, 237019, 238411}As of June 2023, the largest Proth primes discovered are:[11] A Proth number of the second kind is a natural number N of the form
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: k ∈ {23669, 31859, 38473, 46663, 67117, 74699, 81041, 121889, 129007, 143047, 161669, 206231, 215443, 226153, 234343, 245561, 250027, 315929, 319511, 324011, 325123, 327671, 336839, 342847, 344759, 362609, 363343, 364903, 365159, 368411, 371893, 384539, 386801, 397027, 409753, 444637, 470173, 474491, 477583, 485557, 494743 }Small Proth primes (less than 10200) have been used in constructing prime ladders, sequences of prime numbers such that each term is "close" (within about 1011) 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 × 1030 using prime ladders constructed from Proth primes.
[18] (The conjecture was later proved by Harald Helfgott.
[19][20][better source needed]) Also, Proth primes can optimize den Boer reduction between the Diffie–Hellman problem and the Discrete logarithm problem.
[21] 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.