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 ${\displaystyle N-1=q^{k}R}$ where q is a prime which does not divide R. If there is an integer a such that ${\displaystyle a^{n-1}\equiv 1(\mathrm{mod}n)}$ and ${\displaystyle gcd(a^{(N-1)/q}-1,N)=1}$, then each prime factor q of N has the form ${\displaystyle q^{k}r+1}$.

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

Let ${\displaystyle N=fr+1}$, where ${\displaystyle 0<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:

${\displaystyle x_p^{N-1}\equiv 1(\mathrm{mod}N)}$

${\displaystyle 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

${\displaystyle p\equiv 1(\mathrm{mod}f)}$

There are several algorithms which can be used to finish the proof, provided f is big enough. If ${\displaystyle f^3>n}$, Selfridge's test can be used to prove primality. If ${\displaystyle f^{10}>n^3}$, the Konyagin-Pomerance Test can be used. If ${\displaystyle f^4>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 ${\displaystyle f^4<n}$, there is no known algorithm which enhances Pocklington's theorem.

External links

• Pocklington primality test
• Primality proving program based on Pocklington's theorem by Makoto Kamada. It includes a program written in C language that proves primality of numbers of several thousand digits using this theorem.