A

theorem by

Francois Proth^{1} 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.