In mathematics, the Pocklington–Lehmer primality test is a primality test devised by Henry Cabourn Pocklington and Derrick Henry Lehmer. The test uses a partial factorization of N − 1 {\displaystyle N-1} to prove that an integer N {\displaystyle N} is prime. It produces a primality certificate to be found with less effort than the Lucas primality test, which requires the full factorization of N − 1 {\displaystyle N-1} .
Pocklington criterion The basic version of the test relies on the Pocklington theorem (or Pocklington criterion) which is formulated as follows: Let N > 1 {\displaystyle N>1} be an integer, and suppose there exist natural numbers a and p such that
Then N is prime. Here i ≡ j ( mod k ) {\displaystyle i\equiv j{\pmod {k}}} means that after finding the remainder of division by k, i and j are equal; i | j {\displaystyle i\vert j} means that i is a divisor for j; and gcd is the greatest common divisor. 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).) For example, let N = 35 {\displaystyle N=35} . With a = 2 {\displaystyle a=2} , we find that a N − 1 ≡ 9 ( mod N ) {\displaystyle a^{N-1}\equiv 9{\pmod {N}}} . This is enough to prove that N is not prime.
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. The main difficulty is finding a value of p which satisfies (2). First, it is usually difficult to find a large prime factor of a large number. Second, for many primes N, such a p does not exist. For example, N = 17 {\displaystyle N=17} has no suitable p because N − 1 = 2 4 {\displaystyle N-1=2^{4}} , and p = 2 < N − 1 {\displaystyle p=2<{\sqrt {N}}-1} , which violates the inequality in (2); other examples include
N = 19 , 37 , 41 , 61 , 71 , 73 , {\displaystyle N=19,37,41,61,71,73,} and 97 {\displaystyle 97} . Given p, finding a is not nearly as difficult. If N is prime, then by Fermat's little theorem, any a in the interval 1 ≤ a ≤ N − 1 {\displaystyle 1\leq a\leq N-1} will satisfy (1) (however, the cases a = 1 {\displaystyle a=1} and a = N − 1 {\displaystyle a=N-1} are trivial and will not satisfy (3)). This a will satisfy (3) as long as ord(a) does not divide ( N − 1 ) / p {\displaystyle (N-1)/p} . Thus a randomly chosen a in the interval 2 ≤ a ≤ N − 2 {\displaystyle 2\leq a\leq N-2} has a good chance of working. If a is a generator mod N, its order is N − 1 {\displaystyle N-1} and so the method is guaranteed to work for this choice.
Generalized Pocklington test The above version of Pocklington's theorem is sometimes impossible to apply because some primes N {\displaystyle N} are such that there is no prime p {\displaystyle p} dividing N − 1 {\displaystyle N-1} where p > N − 1 {\displaystyle p>{\sqrt {N}}-1} . The following generalized version of Pocklington's theorem is more widely applicable. Theorem: Factor N − 1 as N − 1 = AB, where A and B are relatively prime, A > N {\displaystyle A>{\sqrt {N}}} , the prime factorization of A is known, but the factorization of B is not necessarily known. If for each prime factor p of A there exists an integer a p {\displaystyle a_{p}} so that
then N is prime.
… excerpt ends here. Continue reading the full article.
