Proth's theorem

Proth's theorem In number theory, Proth's theorem is a primality test for Proth numbers.

Il est dit[1][2] that if p is a Proth number, of the form k2n + 1 with k odd and k < 2n, and if there exists an integer a for which {displaystyle a^{frac {p-1}{2}}equiv -1{pmod {p}},} then p is prime. In this case p is called a Proth prime. This is a practical test because if p is prime, any chosen a has about a 50 percent chance of working, furthermore, since the calculation is mod p, only values of a smaller than p have to be taken into consideration. In practice, however, a quadratic nonresidue of p is found via a modified Euclid's algorithm and taken as the value of a, since if a is a quadratic nonresidue modulo p then the converse is also true, and the test is conclusive. For such an a the Legendre symbol is {displaystyle left({frac {a}{p}}right)=-1.} Thus, in contrast to many Monte Carlo primality tests (randomized algorithms that can return a false positive), the primality testing algorithm based on Proth's theorem is a Las Vegas algorithm, always returning the correct answer but with a running time that varies randomly. Note that if a is chosen to be a quadratic nonresidue as described above, the runtime is constant, safe for the time spent on finding such a quadratic nonresidue. Finding such a value is very fast compared to the actual test. Contents 1 Numerical examples 2 Proof 3 History 4 See also 5 References 6 External links Numerical examples Examples of the theorem include: for p = 3 = 1(21) + 1, we have that 2(3-1)/2 + 1 = 3 is divisible by 3, so 3 is prime. for p = 5 = 1(22) + 1, we have that 3(5-1)/2 + 1 = 10 is divisible by 5, so 5 is prime. for p = 13 = 3(22) + 1, we have that 5(13-1)/2 + 1 = 15626 is divisible by 13, so 13 is prime. for p = 9, which is not prime, there is no a such that a(9-1)/2 + 1 is divisible by 9. The first Proth primes are (sequence A080076 in the OEIS): 3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, 449, 577, 641, 673, 769, 929, 1153 …. The largest known Proth prime as of 2016 is {displaystyle 10223cdot 2^{31172165}+1} , and is 9,383,761 digits long.[3] It was found by Peter Szabolcs in the PrimeGrid distributed computing project which announced it on 6 November 2016.[4] It is also the largest known non-Mersenne prime and largest Colbert number.[5] The second largest known Proth prime is {displaystyle 19249cdot 2^{13018586}+1} , found by Seventeen or Bust.[6] Proof The proof for this theorem uses the Pocklington-Lehmer primality test, and closely resembles the proof of Pépin's test. The proof can be found on page 52 of the book by Ribenboim in the references. History François Proth (1852–1879) published the theorem in 1878.[7][8] See also Pépin's test (the special case k = 1, where one chooses a = 3) Sierpinski number References ^ Paulo Ribenboim (1996). The New Book of Prime Number Records. New York, NY: Springer. p. 52. ISBN 0-387-94457-5. ^ Hans Riesel (1994). Prime Numbers and Computer Methods for Factorization (2 ed.). Boston, MA: Birkhauser. p. 104. ISBN 3-7643-3743-5. ^ Chris Caldwell, The Top Twenty: Proth, from The Prime Pages. ^ "World Record Colbert Number discovered!". ^ Chris Caldwell, The Top Twenty: Largest Known Primes, from The Prime Pages. ^ Caldwell, Chris K. "The Top Twenty: Largest Known Primes". ^ François Proth (1878). "Theoremes sur les nombres premiers". Comptes rendus de l'Académie des Sciences de Paris. 87: 926. ^ Leonard Eugene Dickson (1966). History of the Theory of Numbers. Vol. 1. New York, NY: Chelsea. p. 92. External links Weisstein, Eric W. "Proth's Theorem". MathWorld. hide vte Number-theoretic algorithms Primality tests AKSAPRBaillie–PSWElliptic curvePocklingtonFermatLucasLucas–LehmerLucas–Lehmer–RieselProth's theoremPépin'sQuadratic FrobeniusSolovay–StrassenMiller–Rabin Prime-generating Sieve of AtkinSieve of EratosthenesSieve of PritchardSieve of SundaramWheel factorization Integer factorization Continued fraction (CFRAC)Dixon'sLenstra elliptic curve (ECM)Euler'sPollard's rhop − 1p + 1Quadratic sieve (QS)General number field sieve (GNFS)Special number field sieve (SNFS)Rational sieveFermat'sShanks's square formsTrial divisionShor's Multiplication Ancient EgyptianLongKaratsubaToom–CookSchönhage–StrassenFürer's Euclidean division BinaryChunkingFourierGoldschmidtNewton-RaphsonLongShortSRT Discrete logarithm Baby-step giant-stepPollard rhoPollard kangarooPohlig–HellmanIndex calculusFunction field sieve Greatest common divisor BinaryEuclideanExtended EuclideanLehmer's Modular square root CipollaPocklington'sTonelli–ShanksBerlekampKunerth Other algorithms ChakravalaCornacchiaExponentiation by squaringInteger square rootInteger relation (LLL; KZ)Modular exponentiationMontgomery reductionSchoofTrachtenberg system Italics indicate that algorithm is for numbers of special forms Categories: Primality testsTheorems about prime numbers