Topics Register • News • History • How to • Sequences statistics • Template prototypes

# Difference between revisions of "Pocklington's theorem"

The Pocklington's theorem invented by H. C. Pocklington in 1914, which is a primality test for the number N, states:

Let $N-1 = q^k\,R$ where q is a prime which does not divide R. If there is an integer a such that $a^{n-1}\,\equiv\,1\,\pmod{n}$ and $gcd(a^{(N-1)/q}-1,N) = 1$, then each prime factor q of N has the form $q^kr+1$.

From the previous theorem it can be deduced a primality test when only a partial factorization of N-1 is known:

Let $N = fr + 1$, where $0\,\lt \,r\,\le \,f+1$. The value N is prime if, for every prime divisor p of f, there is an integer x_p such that:

$x_p^{N-1}\,\equiv\,1\,\pmod{N}$
$gcd(x_p^{(N-1)/p}\,-1,\,N) = 1$

If f < r, Pocklington's theorem does not return a primality proof, but there is still some hope of proving primality. The theorem implies that every factor p of N satisfies

$p \equiv 1 \pmod{f}$

There are several algorithms which can be used to finish the proof, provided f is big enough. If $f^3 \gt n$, Selfridge's test can be used to prove primality. If $f^{10} \gt n^3$, the Konyagin-Pomerance Test can be used. If $f^4 \gt n$, there is a polynomial-time algorithm, due to Coppersmith and Howgrave-Graham for carrying out a complete search for divisors congruent to 1 modulo f.

Each of these algorithms is more complicated than the last, so it is best to use the simplest one which will work for the value of f you have. For $f^4 \lt n$, there is no known algorithm which enhances Pocklington's theorem.