Proth's Theorem

A theorem by Francois Proth¹ for finding primes:
Let N = k^.2ⁿ+1 with 2ⁿ > k. If there is an integer a such that a^(N-1)/2 = -1 (mod N),
then N is prime.

This test is so simple that the difficulty is quickly multiplying the large numbers involved. It (also?) applies to Cullen Primes, Fermat Factors, and the primes in the Sierpinski Conjecture.

---

¹ Props to wertperch for finding me his first initial and auraseer for his first name.