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.
If a is a quadratic nonresidue modulo p then the converse is also true, and the test is conclusive. Such an a may be found by iterating a over small primes and computing the Jacobi symbol until:
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.
Examples of the theorem include:
The first Proth primes are (sequence in the OEIS):
The largest known Proth prime as of 2016[update] is , and 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 second largest known Proth prime is 19249 · 213018586 + 1, found by Seventeen or Bust.
...
Wikipedia