Pocklington primality test
Encyclopedia
In mathematics, the Pocklington–Lehmer primality test is a primality test
devised by Henry Cabourn Pocklington
and Derrick Henry Lehmer
to decide whether a given number
is prime. The output of the test is a proof that the number is prime or that primality could not be established.
Let
be an integer, and suppose there exist numbers a and q such that
(1) q is prime,
and 
(2)
(3)
Then
is prime.
that divides N.
Therefore,
which implies 
.
Thus there must exist an integer u with the property that
This implies
by (1) and (2), and this contradicts (3)
The test is simple once the theorem above is established. Given N, seek to find suitable a and q. If they can be obtained, then N is prime. Moreover, a and q are the certificate of primality. They can be quickly verified to satisfy the conditions of the theorem, confirming N as prime.
A problem which arises is the ability to find a suitable q, that must satisfy (1)–(3) and be provably prime. It is even quite possible that such a q does not exist. This is a large probability, indeed only 57.8% of the odd primes, N,
have such a q. To find a is not nearly so difficult. If N is prime, and a suitable q is found, each choice of a where 
will satisfy 
, and so will satisfy (2) as long as ord(a) does not divide 
. Thus a randomly chosen a is likely to work. If a is a generator mod N its order is N-1 and so the method is guaranteed to work for this choice.
Corollary:
Let N − 1 factor as N − 1 = AB, where A and B are relatively prime,
and the factorization of A is known.
If for every prime factor p of A there exists an integer
so that
and
then N is prime. The reverse implication also holds: If N is prime then every prime factor of A can be written in the above manner.
Proof of Corollary:
Let p be a prime dividing A and let
be the maximum power of p dividing A.
Let v be a prime factor of N. For the
from the corollary set
. This means
and because of 
also
.
This means that the order of
is 
Thus,
. The same observation holds for each prime power factor 
of A,
which implies
.
Specifically, this means
If N were composite, it would necessarily have a prime factor which is less than or equal to
. It has been shown that there is no such factor, which implies that N is prime.
To see the converse choose
a generator of the integers modulo p.
for every prime factor p of A, which fulfills the conditions of the corollary. If such 
's can be found, the Corollary implies that N is prime.
According to Koblitz,
= 2 often works.
Choose
, which means 
Now it is clear that
and 
.
Next find an
for each prime factor p of A.
E.g. choose
.
So
satisfies the necessary conditions. Choose 
.
and
So both
's work and thus N is prime.
We have chosen a small prime for calculation purposes but in practice when we start factoring A we will get factors that themselves must be checked for primality. It is not a proof of primality until we know our factors of A are prime as well. If we get a factor of A where primality is not certain, the test must be performed on this factor as well. This gives rise to a so-called down-run procedure, where the primality of a number is evaluated via the primality of a series of smaller numbers.
In our case, we can say with certainty that 2, 5, and 227 are prime, and thus we have proved our result. The certificate in our case is the list of
's, which can quickly be checked in the corollary.
If our example had given rise to a down-run sequence, the certificate would be more complicated. It would first consist of our initial round of
's which correspond to the 'prime' factors of A; Next, for the factor(s) of A of which primality was uncertain, we would have more 
's, and so on for factors of these factors until we reach factors of which primality is certain. This can continue for many layers if the initial prime is large, but the important thing to note, is that a simple certificate can be produced, containing at each level the prime to be tested, and the corresponding 
's, which can easily be verified. If at any level we cannot find 
's then we cannot say that N is prime.
The biggest difficulty with this test is the necessity of discovering prime factors of N - 1, in essence, factoring N − 1. In practice this could be extremely difficult. Finding
's is a less difficult problem.
Primality test
A primality test is an algorithm for determining whether an input number is prime. Amongst other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating whether the input number is prime or not...
devised by Henry Cabourn Pocklington
Henry Cabourn Pocklington
Henry Cabourn Pocklington was an English physicist and mathematician. His primary profession was as a schoolmaster, but he has made important contributions to number theory with the discovery of Pocklington's primality test in 1914.-References:...
and Derrick Henry Lehmer
Derrick Henry Lehmer
Derrick Henry "Dick" Lehmer was an American mathematician who refined Édouard Lucas' work in the 1930s and devised the Lucas–Lehmer test for Mersenne primes...
to decide whether a given number
is prime. The output of the test is a proof that the number is prime or that primality could not be established.Pocklington criterion
The test relies on the Pocklington Theorem (Pocklington criterion) which is formulated as follows:Let
be an integer, and suppose there exist numbers a and q such that(1) q is prime,
and (2)
(3)
Then
is prime.Proof of this theorem
Suppose N is not prime. This means there must be a prime p, where that divides N.Therefore,
which implies .Thus there must exist an integer u with the property that
This implies
by (1) and (2), and this contradicts (3)
The test is simple once the theorem above is established. Given N, seek to find suitable a and q. If they can be obtained, then N is prime. Moreover, a and q are the certificate of primality. They can be quickly verified to satisfy the conditions of the theorem, confirming N as prime.
A problem which arises is the ability to find a suitable q, that must satisfy (1)–(3) and be provably prime. It is even quite possible that such a q does not exist. This is a large probability, indeed only 57.8% of the odd primes, N,
have such a q. To find a is not nearly so difficult. If N is prime, and a suitable q is found, each choice of a where will satisfy , and so will satisfy (2) as long as ord(a) does not divide . Thus a randomly chosen a is likely to work. If a is a generator mod N its order is N-1 and so the method is guaranteed to work for this choice.Generalized Pocklington method
A generalized version of Pocklington's theorem covers more primes N.Corollary:
Let N − 1 factor as N − 1 = AB, where A and B are relatively prime,
and the factorization of A is known.If for every prime factor p of A there exists an integer
so that
and
then N is prime. The reverse implication also holds: If N is prime then every prime factor of A can be written in the above manner.Proof of Corollary:
Let p be a prime dividing A and let
be the maximum power of p dividing A.Let v be a prime factor of N. For the
from the corollary set. This means and because of also.This means that the order of
is Thus,
. The same observation holds for each prime power factor of A,which implies
.Specifically, this means
If N were composite, it would necessarily have a prime factor which is less than or equal to
. It has been shown that there is no such factor, which implies that N is prime.To see the converse choose
a generator of the integers modulo p.The test
The Pocklington–Lehmer primality test follows directly from this corollary. We must first partially factor N − 1 into A and B. Then we must find an for every prime factor p of A, which fulfills the conditions of the corollary. If such 's can be found, the Corollary implies that N is prime.According to Koblitz,
= 2 often works.Example
Choose
, which means Now it is clear that
and .Next find an
for each prime factor p of A.E.g. choose
.-
.
So
satisfies the necessary conditions. Choose .
and
So both
's work and thus N is prime.We have chosen a small prime for calculation purposes but in practice when we start factoring A we will get factors that themselves must be checked for primality. It is not a proof of primality until we know our factors of A are prime as well. If we get a factor of A where primality is not certain, the test must be performed on this factor as well. This gives rise to a so-called down-run procedure, where the primality of a number is evaluated via the primality of a series of smaller numbers.
In our case, we can say with certainty that 2, 5, and 227 are prime, and thus we have proved our result. The certificate in our case is the list of
's, which can quickly be checked in the corollary.If our example had given rise to a down-run sequence, the certificate would be more complicated. It would first consist of our initial round of
's which correspond to the 'prime' factors of A; Next, for the factor(s) of A of which primality was uncertain, we would have more 's, and so on for factors of these factors until we reach factors of which primality is certain. This can continue for many layers if the initial prime is large, but the important thing to note, is that a simple certificate can be produced, containing at each level the prime to be tested, and the corresponding 's, which can easily be verified. If at any level we cannot find 's then we cannot say that N is prime.The biggest difficulty with this test is the necessity of discovering prime factors of N - 1, in essence, factoring N − 1. In practice this could be extremely difficult. Finding
's is a less difficult problem.