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