In mathematics, the Pocklington–Lehmer primality test is a primality test devised by Henry Cabourn Pocklington[1] and Derrick Henry Lehmer.
It produces a primality certificate to be found with less effort than the Lucas primality test, which requires the full factorization of
be an integer, and suppose there exist natural numbers a and p such that Then N is prime.
means that after finding the remainder of division by k, i and j are equal;
Note: Equation (1) is simply a Fermat primality test.
If we find any value of a, not divisible by N, such that equation (1) is false, we may immediately conclude that N is not prime.
(This divisibility condition is not explicitly stated because it is implied by equation (3).)
Thus there must exist an integer u, a multiplicative inverse of p modulo q−1, with the property that and therefore, by Fermat's little theorem This implies This shows that q divides the
[3] Given N, if p and a can be found which satisfy the conditions of the theorem, then N is prime.
Moreover, the pair (p, a) constitute a primality certificate which can be quickly verified to satisfy the conditions of the theorem, confirming N as prime.
This a will satisfy (3) as long as ord(a) does not divide
and so the method is guaranteed to work for this choice.
The above version of Pocklington's theorem is sometimes impossible to apply because some primes
The following generalized version of Pocklington's theorem is more widely applicable.
[5]: Corollary 1 Theorem: Factor N − 1 as N − 1 = AB, where A and B are relatively prime,
The same observation holds for each prime power factor
If N were composite, it would necessarily have a prime factor which is less than or equal to
The Pocklington–Lehmer primality test follows directly from this corollary.
Finally, for each prime factor p of A, use trial and error to find an ap that satisfies (6) and (7).
to this high power can be done efficiently using binary exponentiation: So,
We have chosen small numbers for this example, but in practice when we start factoring A we may get factors that are themselves so large their primality is not obvious.
In such a case we use the same test recursively on the large factors of A, until all of the primes are below a reasonable threshold.
In our example, we can say with certainty that 2 and 3 are prime, and thus we have proved our result.
pairs, which can be quickly checked in the corollary.
If our example had included large prime factors, the certificate would be more complicated.
This can continue for many layers if the initial prime is large, but the important point is that a certificate can be produced, containing at each level the prime to be tested, and the corresponding aps, which can easily be verified.
The 1975 paper by Brillhart, Lehmer, and Selfridge[5] gives a proof for what is shown above as the "generalized Pocklington theorem" as Theorem 4 on page 623.
Additional theorems are shown which allow less factoring.
Theorem 5 of the Brillhart, Lehmer, and Selfridge paper allows a primality proof when the factored part has reached only
Many additional such theorems are presented that allow one to prove the primality of N based on the partial factorization of