Proth prime


A Proth number is a 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
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.

Large primes

, the largest known Proth prime is. It is 9,383,761 digits long. It was found by Szabolcs Peter in the PrimeGrid distributed computing project which announced it on 6 November 2016. It is also the 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, 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:
k ∈
As of December 2019, the largest Proth primes discovered are:
rankprimedigitswhenCullen prime?Discoverer References
110223 · 231172165 + 1938376131 Oct 2016Szabolcs Péter
2168451 · 219375200 + 1583252217 Sep 2017Ben Maloney
319249 · 213018586 + 1391899026 Mar 2007Konstantin Agafonov
4193997 · 211452891 + 134476703 Apr 2018Tom Greer
53 · 210829346 + 1325995914 Jan 2014Sai Yik Tang
627653 · 29167433 + 127596778 Jun 2005Derek Gordon
790527 · 29162167 + 1275809330 Jun 2010Unknown
828433 · 27830457 + 1235720730 Dec 2004Team Prime Rib
9161041 · 27107964 + 121397166 Jan 2015Martin Vanc
1027 · 27046834 + 1212131011 Oct 2018Andrew M. Farrow
113 · 27033641 + 1211733821 Feb 2011Michael Herder
1233661 · 27031232 + 1211661717 Oct 2007Sturle Sunde
136679881 · 26679881 + 1201085225 Jul 2009YesMagnus Bergman
141582137 · 26328550 + 1190509020 Apr 2009YesDennis R. Gesker
157 · 25775996 + 117387492 Nov 2012Martyn Elvy
169 · 25642513 + 1169856729 Nov 2013Serge Batalov
17258317 · 25450519 + 1164077628 Jul 2008Scott Gilvey
1827 · 25213635 + 115694629 Mar 2015Hiroyuki Okazaki
1939 · 25119458 + 1154111323 Nov 2019Scott Brown
203 · 25082306 + 115299283 Apr 2009Andy Brady

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·1030 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 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.