Proth's algorithm

Proth's theorem states that if n=2mh+1, 0 < h < 2m, 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.)

Enter h (> 0 and odd):
Enter m ( h < 2m, m ≤ 1000):

Last modified 20th January 2005
Return to main page