Proth prime

From Wikipedia, the free encyclopedia
  (Redirected from Proth number)
Jump to navigation Jump to search
Proth prime
Named afterFrançois Proth
Publication year1878
Author of publicationProth, Francois
No. of known termsOver 1.5 billion below 270
Conjectured no. of termsInfinite
Subsequence ofProth numbers, prime numbers
Formulak × 2n + 1
First terms3, 5, 13, 17, 41, 97, 113
Largest known term10223 × 231172165 + 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

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.[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 (OEISA080076).

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

Definition[edit]

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.[1][2]

Without the condition that , all odd integers larger than 1 would be Proth numbers.[3]

Primality testing[edit]

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

[2][4]

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.[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 (e.g. Cullen prime search). In these cases algorithm runs in at most , or time for all . There is also an algorithm that runs in time.[1][5]

Large primes[edit]

As of 2019, the largest known Proth prime is . 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 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.

Since divisors of Fermat numbers are always of the form , it is customary to determine if a new Proth prime divides a Fermat number.[9]

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 , also called Thabit primes of the second kind)
  • 27121 Prime Search (searching for primes of the form and )
  • Cullen prime search (searching for primes of the form )
  • Sierpinski problem (and their prime and extended generalizations) – searching for primes of the form 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:[10]

rank prime digits when Comments Discoverer (Project) References
1 10223 × 231172165 + 1 9383761 31 Oct 2016 Szabolcs Péter (Sierpinski Problem) [11]
2 168451 × 219375200 + 1 5832522 17 Sep 2017 Ben Maloney (Prime Sierpinski Problem) [12]
3 7 × 218233956 + 1 5488969 1 Oct 2020 Divides Fermat F18233954 Ryan Propper (LLR) [13]
4 3 × 216408818 + 1 4939547 28 Oct 2020 Divides generalized Fermat F16408814(3) and F16408817(5) James Brown (PrimeGrid) [14]
5 (27658613 + 1) × 27658614 + 1 4610945 31 Jul 2020 Gaussian Mersenne norm Ryan Propper and Serge Batalov [10]
6 99739 × 214019102 + 1 4220176 24 Dec 2019 Brian Niegocki (Extended Sierpinski) [15]
7 404849 × 213764867 + 1 4143644 10 Mar 2021 Generalized Cullen with base 131072 Ryan Propper and Serge Batalov [10]
8 9 × 213334487 + 1 4014082 31 Mar 2020 Divides F13334485(3) Ryan Propper [14]
9 19249 × 213018586 + 1 3918990 26 Mar 2007 Konstantin Agafonov (Seventeen or Bust) [11]
10 9 × 212406887 + 1 3734847 29 Mar 2020 Divides F12406885(3) Ryan Propper [14]
11 27 × 212184319 + 1 3667847 6 Feb 2021 Ryan Propper [10]
12 9 × 211500843 + 1 3462100 13 Mar 2020 Divides F11500840(12) Ryan Propper [14]
13 193997 × 211452891 + 1 3447670 3 Apr 2018 Tom Greer (Extended Sierpinski Problem) [16]
14 9 × 211366286 + 1 3421594 26 Mar 2020 Ryan Propper [14]
15 9 × 211158963 + 1 3359184 13 Mar 2020 Divides F11158962(5) Ryan Propper [14]
16 3 × 210829346 + 1 3259959 14 Jan 2014 Divides F10829343(3) and F10829345(5) Sai Yik Tang (321 Prime Search) [17]
17 9 × 29778263 + 1 2943552 5 Aug 2020 Divides F9778262(7) Ryan Propper [14]
18 121 × 29584444 + 1 2885208 20 Nov 2020 James Winskill (27121 Prime Search) [18]
19 11 × 29381365 + 1 2824704 7 Mar 2020 Divides F9381364(6) Ryan Propper [14]
20 27653 × 29167433 + 1 2759677 8 Jun 2005 Derek Gordon (Seventeen or Bust) [11]

Uses[edit]

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.[19] (The conjecture was later proved by Harald Helfgott.[20][21][better source needed])

Also, Proth primes can optimize den Boer reduction between the Diffie-Hellman problem and the Discrete logarithm problem. The prime number 55 × 2286 + 1 has been used in this way.[22]

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

References[edit]

  1. ^ a b c Sze, Tsz-Wo (2008). "Deterministic Primality Proving on Proth Numbers". arXiv:0812.2596 [math.NT].
  2. ^ a b 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. ^ "The Prime Glossary: Fermat divisor". primes.utm.edu. Retrieved 14 November 2021.
  10. ^ a b c d Caldwell, Chris K. "The top twenty: Proth". The Top Twenty. Retrieved 6 December 2019.
  11. ^ a b c Goetz, Michael (27 February 2018). "Seventeen or Bust". PrimeGrid. Retrieved 6 Dec 2019.
  12. ^ "Official discovery of the prime number 168451×219375200+1" (PDF). PrimeGrid. Retrieved 6 Dec 2019.
  13. ^ "Fermat factoring status". www.prothsearch.com. Retrieved 14 November 2021.
  14. ^ a b c d e f g h "New GFN factors". www.prothsearch.com. Retrieved 14 November 2021.
  15. ^ "Official discovery of the prime number 99739×214019102+1" (PDF). PrimeGrid. 24 December 2019. Retrieved 14 November 2021.
  16. ^ "Official discovery of the prime number 193997×211452891+1" (PDF). PrimeGrid. Retrieved 6 Dec 2019.
  17. ^ "Official discovery of the prime number 3×210829346+1" (PDF). PrimeGrid. Retrieved 6 Dec 2019.
  18. ^ "Official discovery of the prime number 121×29584444+1" (PDF). PrimeGrid. Retrieved 14 November 2021.
  19. ^ Helfgott, H. A.; Platt, David J. (2013). "Numerical Verification of the Ternary Goldbach Conjecture up to 8.875e30". arXiv:1305.3062 [math.NT].
  20. ^ Helfgott, Harald A. (2013). "The ternary Goldbach conjecture is true". arXiv:1312.7748 [math.NT].
  21. ^ "Harald Andrés Helfgott". Alexander von Humboldt-Professur. Retrieved 2019-12-08.
  22. ^ 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.
  23. ^ Acar, Tolga; Shumow, Dan (2010). "Modular Reduction without Pre-Computation for Special Moduli" (PDF). Microsoft Research.