A theorem by Francois Proth1 for finding primes:
Let N = k.2n+1 with 2n > 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.

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

Log in or registerto write something here or to contact authors.