### Proth's algorithm

Proth's theorem states that if n=2^{m}h+1, 0 < h < 2^{m}, h odd and n divides a^{(n-1)/2} +1, a > 1, then n is prime.
(See H. Riesel, *Prime numbers and computer methods for factorization*, p. 110 or MP313 notes.)

*Last modified 20th January 2005*

Return to main page