Proth's theorem

In number theory, Proth's theorem is a primality test for Proth numbers. It states 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 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 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. 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 : 3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, 449, 577, 641, 673, 769, 929, 1153 .... The largest known Proth prime is , and is 9,383,761 digits long. It was found by Peter Szabolcs in the PrimeGrid volunteer computing project which announced it on 6 November 2016. It is also the largest known non-Mersenne prime and largest Colbert number. The second largest known Proth prime is , found by PrimeGrid.