Proth prime

A Proth number is a number N of the form ${\displaystyle N=k2^{n}+1}$ where k and n are positive integers, k is odd and ${\displaystyle 2^{n}>k}$. A Proth prime is a Proth number that is prime. They are named after the French mathematician François Proth.[1] The first few Proth primes are

3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, 449, 577, 641, 673, 769, 929, 1153, 1217, 1409, 1601, 2113, 2689, 2753, 3137, 3329, 3457, 4481, 4993, 6529, 7297, 7681, 7937, 9473, 9601, 9857 (OEIS: A080076).

Proth prime

Named after	François Proth
Publication year	1878
Author of publication	Proth, Francois
No. of known terms	Over 1.5 billion below 2^70
Conjectured no. of terms	Infinite
Subsequence of	Proth numbers, prime numbers
Formula	k × 2^n + 1
First terms	3, 5, 13, 17, 41, 97, 113
Largest known term	10223 × 2^31172165 + 1 (as of December 2019)
OEIS index	A080076 Proth primes: primes of the form k*2^m + 1 with odd k < 2^m, m >= 1

The primality of Proth numbers can be tested more easily than many other numbers of similar magnitude.

Definition

A Proth number takes the form ${\displaystyle N=k2^{n}+1}$ where k and n are positive integers, ${\displaystyle k}$ is odd and ${\displaystyle 2^{n}>k}$. A Proth prime is a Proth number that is prime.[1][2]

Without the condition that ${\displaystyle 2^{n}>k}$, all odd integers larger than 1 would be Proth numbers.[3]

Primality testing

See also: Proth's theorem

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

${\displaystyle a^{\frac {p-1}{2}}\equiv -1{\pmod {p}}.}$[2][4]

This theorem can be used as a probabilistic test of primality, by checking for many random choices of ${\displaystyle a}$ whether ${\displaystyle a^{\frac {p-1}{2}}\equiv -1{\pmod {p}}.}$ If this fails to hold for several random ${\displaystyle a}$, then it is very likely that the number ${\displaystyle p}$ 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 ${\displaystyle {\tilde {O}}((k\log k+\log N)(\log N)^{2})}$ time, where Õ is the soft-O notation. For typical searches for Proth primes, usually ${\displaystyle k}$ is either fixed (e.g. 321 Prime Search or Sierpinski Problem) or of order ${\displaystyle O(\log N)}$ (e.g. Cullen prime search). In these cases algorithm runs in at most ${\displaystyle {\tilde {O}}((\log N)^{3})}$, or ${\displaystyle O((\log N)^{3+\epsilon })}$ time for all ${\displaystyle \epsilon >0}$. There is also an algorithm that runs in ${\displaystyle {\tilde {O}}((\log N)^{24/7})}$ time.[1][5]

Large primes

As of 2019, the largest known Proth prime is ${\displaystyle 10223\cdot 2^{31172165}+1}$. It is 9,383,761 digits long.[6] It was found by Szabolcs Peter in the PrimeGrid distributed computing project which announced it on 6 November 2016.[7] It is also the largest known non-Mersenne prime.[8]

The project Seventeen or Bust, searching for Proth primes with a certain ${\displaystyle t}$ to prove that 78557 is the smallest Sierpinski number (Sierpinski problem), has found 11 large Proth primes by 2007, of which 5 are megaprimes. Similar resolutions to the prime Sierpiński problem and extended Sierpiński problem have yielded several more numbers.

As of December 2019, 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 ${\displaystyle 3\times 2^{n}+1}$, also called Thabit primes of the second kind)
• 27121 Prime Search (searching for primes of the form ${\displaystyle 27\times 2^{n}+1}$ and ${\displaystyle 121\times 2^{n}+1}$)
• Cullen prime search (searching for primes of the form ${\displaystyle n\times 2^{n}+1}$)
• Sierpinski problem (and their prime and extended generalizations) - searching for primes of the form ${\displaystyle k\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, 202705, 209611, 222113, 225931, 227723, 229673, 237019, 238411}

As of December 2019, the largest Proth primes discovered are:[9]

rank	prime	digits	when	Cullen prime?	Discoverer (Project)	References
1	10223 · 2^31172165 + 1	9383761	31 Oct 2016		Szabolcs Péter (Sierpinski Problem)	[10]
2	168451 · 2^19375200 + 1	5832522	17 Sep 2017		Ben Maloney (Prime Sierpinski Problem)	[11]
3	19249 · 2^13018586 + 1	3918990	26 Mar 2007		Konstantin Agafonov (Seventeen or Bust)	[10]
4	193997 · 2^11452891 + 1	3447670	3 Apr 2018		Tom Greer (Extended Sierpinski Problem)	[12]
5	3 · 2^10829346 + 1	3259959	14 Jan 2014		Sai Yik Tang (321 Prime Search)	[13]
6	27653 · 2^9167433 + 1	2759677	8 Jun 2005		Derek Gordon (Seventeen or Bust)	[10]
7	90527 · 2^9162167 + 1	2758093	30 Jun 2010		Unknown (Prime Sierpinski Problem)	[14][15]
8	28433 · 2^7830457 + 1	2357207	30 Dec 2004		Team Prime Rib (Seventeen or Bust)	[10]
9	161041 · 2^7107964 + 1	2139716	6 Jan 2015		Martin Vanc (Extended Sierpinski Problem)	[16]
10	27 · 2^7046834 + 1	2121310	11 Oct 2018		Andrew M. Farrow (27121 Prime Search)	[17]
11	3 · 2^7033641 + 1	2117338	21 Feb 2011		Michael Herder (321 Prime Search)	[18]
12	33661 · 2^7031232 + 1	2116617	17 Oct 2007		Sturle Sunde (Seventeen or Bust)	[10]
13	6679881 · 2^6679881 + 1	2010852	25 Jul 2009	Yes	Magnus Bergman (Cullen Prime Search)	[19]
14	1582137 · 2^6328550 + 1	1905090	20 Apr 2009	Yes	Dennis R. Gesker (Cullen Prime Search)	[20]
15	7 · 2^5775996 + 1	1738749	2 Nov 2012		Martyn Elvy (Proth Prime Search)	[21]
16	9 · 2^5642513 + 1	1698567	29 Nov 2013		Serge Batalov	[22][23][nb 1]
17	258317 · 2^5450519 + 1	1640776	28 Jul 2008		Scott Gilvey (Prime Sierpinski Problem)	[14][24]
18	27 · 2^5213635 + 1	1569462	9 Mar 2015		Hiroyuki Okazaki (27121 Prime Search)	[25]
19	39 · 2^5119458 + 1	1541113	23 Nov 2019		Scott Brown (Fermat Divisor Prime Search)	[26]
20	3 · 2^5082306 + 1	1529928	3 Apr 2009		Andy Brady (321 Prime Search)	[27]

1. It remains unclear about which project did Batalov join to find the prime; however, we can be sure that he did not use PrimeGrid.

Uses

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.[28] (The conjecture was later proved by Harald Helfgott.[29][30])

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.[31]

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.[32]

References

1. Sze, Tsz-Wo (2008). "Deterministic Primality Proving on Proth Numbers". arXiv:0812.2596 [math.NT].
2. Weisstein, Eric W. "Proth Prime". mathworld.wolfram.com. Retrieved 2019-12-06.
3. Weisstein, Eric W. "Proth Number". mathworld.wolfram.com. Retrieved 2019-12-07.
4. Weisstein, Eric W. "Proth's Theorem". MathWorld.
5. Konyagin, Sergei; Pomerance, Carl (2013), Graham, Ronald L.; Nešetřil, Jaroslav; Butler, Steve (eds.), "On Primes Recognizable in Deterministic Polynomial Time", The Mathematics of Paul Erdős I, Springer New York, pp. 159–186, doi:10.1007/978-1-4614-7258-2_12, ISBN 978-1-4614-7258-2
6. Caldwell, Chris. "The Top Twenty: Proth". The Prime Pages.
7. Van Zimmerman (30 Nov 2016) [9 Nov 2016]. "World Record Colbert Number discovered!". PrimeGrid.
8. Caldwell, Chris. "The Top Twenty: Largest Known Primes". The Prime Pages.
9. Caldwell, Chris K. "The top twenty: Proth". The Top Twenty. Retrieved 6 December 2019.
10. Goetz, Michael (27 February 2018). "Seventeen or Bust". PrimeGrid. Retrieved 6 Dec 2019.
11. "Official discovery of the prime number 168451×2^19375200+1" (PDF). PrimeGrid. Retrieved 6 Dec 2019.
12. "Official discovery of the prime number 193997×2^11452891+1" (PDF). PrimeGrid. Retrieved 6 Dec 2019.
13. "Official discovery of the prime number 3×2^10829346+1" (PDF). PrimeGrid. Retrieved 6 Dec 2019.
14. "The Prime Sierpinski Problem". mersenneforum.org. 18 Jun 2004. Retrieved 7 December 2019.
15. Caldwell, Chris K. "Patrice Salah". The Prime Pages. Retrieved 9 December 2019.
16. "Official discovery of the prime number 161041×2^7107964+1" (PDF). PrimeGrid. Retrieved 6 Dec 2019.
17. "Official discovery of the prime number 27×2^7046834+1" (PDF). PrimeGrid. Retrieved 6 Dec 2019.
18. "Official discovery of the prime number 3×2^7033641+1" (PDF). PrimeGrid. Retrieved 6 Dec 2019.
19. "Official discovery of the prime number 6679881×2^6679881+1" (PDF). PrimeGrid. Retrieved 6 Dec 2019.
20. "Official discovery of the prime number 6328548×2^6328548+1" (PDF). PrimeGrid. Retrieved 6 Dec 2019.
21. "Official discovery of the prime number 7×2^5775996+1" (PDF). PrimeGrid. Retrieved 6 Dec 2019.
22. "Suggestion: a 5-7-9 Proth project". PrimeGrid. 25 Jul 2019. Retrieved 8 Dec 2019.
23. "9·2^5642513+1 (Another of the Prime Pages' resources)". The Prime Database. 1 April 2014. Retrieved 9 December 2019.
24. Caldwell, Chris K. "Scott Gilvey". The Prime Pages. Retrieved 9 December 2019.
25. "Official discovery of the prime number 27×2^5213635+1" (PDF). PrimeGrid. Retrieved 6 Dec 2019.
26. "PrimeGrid Primes". PrimeGrid. Retrieved 7 December 2019.
27. "Official discovery of the prime number 3×2^5082306+1" (PDF). PrimeGrid. Retrieved 6 Dec 2019.
28. Helfgott, H. A.; Platt, David J. (2013). "Numerical Verification of the Ternary Goldbach Conjecture up to 8.875e30". arXiv:1305.3062 [math.NT].
29. Helfgott, Harald A. (2013). "The ternary Goldbach conjecture is true". arXiv:1312.7748 [math.NT].
30. "Harald Andrés Helfgott". Alexander von Humboldt-Professur. Retrieved 2019-12-08.
31. Brown, Daniel R. L. (24 Feb 2015). "CM55: special prime-field elliptic curves almost optimizing den Boer's reduction between Diffie–Hellman and discrete logs" (PDF). International Association for Cryptologic Research: 1–3.
32. Acar, Tolga; Shumow, Dan (2010). "Modular Reduction without Pre-Computation for Special Moduli" (PDF). Microsoft Research.