Proth prime

A Proth number takes the form $N=k\; 2^n\; +1$ where k and n are positive integers, $k$ is odd and $2^n>k$. A Proth prime is a Proth number that is prime.{{Cite web|url=http://mathworld.wolfram.com/ProthPrime.html|title=Proth Prime|last=Weisstein|first=Eric W.|website=mathworld.wolfram.com|language=en|access-date=2019-12-06}} Without the condition that $2^n\; >\; k$, all odd integers larger than 1 would be Proth numbers.{{Cite web|url=http://mathworld.wolfram.com/ProthNumber.html|title=Proth Number|last=Weisstein|first=Eric W.|website=mathworld.wolfram.com|language=en|access-date=2019-12-07}}

{{See also|Proth's theorem}}

The primality of a Proth number can be tested with Proth's theorem, which states that a Proth number $p$ is prime if and only if there exists an integer $a$ for which

:$a^\{\backslash frac\{p-1\}\{2\}\}\backslash equiv\; -1\; \backslash pmod\{p\}.${{MathWorld|title=Proth's Theorem|id=ProthsTheorem}}

This theorem can be used as a probabilistic test of primality, by checking for many random choices of $a$ whether $a^\{\backslash frac\{p-1\}\{2\}\}\backslash equiv\; -1\; \backslash pmod\{p\}.$ If this fails to hold for several random $a$, then it is very likely that the number $p$ is composite.{{cn|date=December 2019}}

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 $\backslash tilde\{O\}((k\backslash log\; k+\backslash log\; N)(\backslash log\; N)^2)$ time, where Õ is the soft-O notation. For typical searches for Proth primes, usually $k$ is either fixed (e.g. 321 Prime Search or Sierpinski Problem) or of order $O(\backslash log\; N)$ (e.g. Cullen prime search). In these cases algorithm runs in at most $\backslash tilde\{O\}((\backslash log\; N)^3)$, or $O((\backslash log\; N)^\{3+\backslash epsilon\})$ time for all $\backslash epsilon>0$. There is also an algorithm that runs in $\backslash tilde\{O\}((\backslash log\; N)^\{24/7\})$ time.{{Citation|last1=Konyagin|first1=Sergei|title=On Primes Recognizable in Deterministic Polynomial Time|date=2013|work=The Mathematics of Paul Erdős I|pages=159–186|editor-last=Graham|editor-first=Ronald L.|publisher=Springer New York|language=en|doi=10.1007/978-1-4614-7258-2_12|isbn=978-1-4614-7258-2|last2=Pomerance|first2=Carl|editor2-last=Nešetřil|editor2-first=Jaroslav|editor3-last=Butler|editor3-first=Steve}}

Fermat numbers are a special case of Proth numbers, wherein {{math|k{{=}}1}}. In such a scenario Pépin's test proves that only base {{math|a{{=}}3}} need to be checked to deterministically verify or falsify the primality of a Fermat number.

{{as of|2022}}, the largest known Proth prime is $10223\; \backslash times\; 2^\{31172165\}\; +\; 1$. It is 9,383,761 digits long.{{Cite web|url=http://primes.utm.edu/top20/page.php?id=66|title=The Top Twenty: Proth|last=Caldwell|first=Chris|publisher=The Prime Pages}} It was found by Szabolcs Peter in the PrimeGrid volunteer computing project which announced it on 6 November 2016.{{Cite web|url=http://www.primegrid.com/forum_thread.php?id=7116|title=World Record Colbert Number discovered!|author=Van Zimmerman|date=30 Nov 2016|publisher=PrimeGrid|orig-year=9 Nov 2016}} It is also the third largest known non-Mersenne prime.{{Cite web|url=http://primes.utm.edu/top20/page.php?id=3|title=The Top Twenty: Largest Known Primes|last=Caldwell|first=Chris|publisher=The Prime Pages}}

The project Seventeen or Bust, searching for Proth primes with a certain $t$ 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.

Since divisors of Fermat numbers $F\_n\; =\; 2^\{2^n\}\; +\; 1$ are always of the form $k\; \backslash times\; 2^\{n+2\}\; +\; 1$, it is customary to determine if a new Proth prime divides a Fermat number.{{cite web |title=The Prime Glossary: Fermat divisor |url=https://primes.utm.edu/glossary/xpage/FermatDivisor.html |website=primes.utm.edu |access-date=14 November 2021}}

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 (searching for primes of the form $3\backslash times2^n+1$, also called Thabit primes of the second kind)
• 27121 Prime Search (searching for primes of the form $27\backslash times2^n+1$ and $121\backslash times2^n+1$)
• Cullen prime search (searching for primes of the form $n\backslash times2^n+1$)
• Sierpinski problem (and their prime and extended generalizations) – searching for primes of the form $k\; \backslash times\; 2^n+1$ where k is in this list:

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:{{Cite web|url=https://primes.utm.edu/top20/page.php?id=66|title=The top twenty: Proth|last=Caldwell|first=Chris K.|website=The Top Twenty|access-date=6 December 2019}}

A Proth number of the second kind is a natural number N of the form $N\; =\; k\; \backslash times\; 2^n-1$ where k and n are positive integers, k is odd and $2^n\; >\; k$. 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

:3, 7, 11, 23, 31, 47, 79, 127, 191, 223, 239, 383, 479, 607, 863, 991, 1087, 1151, 1279, 1471, 1663, 2111, 2239, 2687, 2879, 3391, 3583, 3967, 5119, 5503, 6143, 6271, 6911, 7039, 8191, 8447, 8831, 9343 ({{OEIS2C|id=A112715}}).

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 (searching for primes of the form $3\backslash times2^n-1$, also called Thabit primes)
• 27121 Prime Search (searching for primes of the form $27\backslash times2^n-1$ and $121\backslash times2^n-1$)
• Woodall prime search (searching for primes of the form $n\backslash times2^n-1$)
• Riesel problem (and their prime and extended generalizations) – searching for primes of the form $k\; \backslash times\; 2^n-1$ where k is in this list:

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 10²⁰⁰) have been used in constructing prime ladders, sequences of prime numbers such that each term is "close" (within about 10¹¹) 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.{{cite arXiv|eprint=1305.3062|title=Numerical Verification of the Ternary Goldbach Conjecture up to 8.875e30|last1=Helfgott|first1=H. A.|last2=Platt|first2=David J.|class=math.NT|year=2013}} (The conjecture was later proved by Harald Helfgott.{{cite arXiv|eprint=1312.7748|class=math.NT|first=Harald A.|last=Helfgott|title=The ternary Goldbach conjecture is true|year=2013}}{{Cite news|url=https://www.humboldt-professur.de/en/preistraeger/preistraeger-2015/helfgott-harald-andres|title=Harald Andrés Helfgott|website=Alexander von Humboldt-Professur|access-date=2019-12-08}}{{better source|date=December 2019}})

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.{{Cite journal|last=Brown|first=Daniel R. L.|date=24 Feb 2015|title=CM55: special prime-field elliptic curves almost optimizing den Boer's reduction between Diffie–Hellman and discrete logs|url=https://eprint.iacr.org/2014/877.pdf|journal=International Association for Cryptologic Research|pages=1–3}}

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.{{Cite journal|last1=Acar|first1=Tolga|last2=Shumow|first2=Dan|date=2010|title=Modular Reduction without Pre-Computation for Special Moduli|url=https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/modmul_no_precomp.pdf|journal=Microsoft Research}}

{{reflist}}

{{Prime number classes}}

Category:Classes of prime numbers

Category:Eponymous numbers in mathematics