Proth's theorem

It states[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 then p is 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[citation needed] 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.

[3] It was found by Peter Szabolcs in the PrimeGrid volunteer computing project which announced it on 6 November 2016.