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 ${\displaystyle N-1}$ to prove that an integer ${\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 ${\displaystyle N-1}$.

The basic version of the test relies on the Pocklington theorem (or Pocklington criterion) which is formulated as follows:

Let ${\displaystyle N>1}$ be an integer, and suppose there exist natural numbers a and p such that

Then N is prime. Here ${\displaystyle i\equiv j{\pmod {k}}}$ means that after finding the remainder of division by k, i and j are equal; ${\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 ${\displaystyle N=35}$. With ${\displaystyle a=2}$, we find that ${\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, ${\displaystyle N=17}$ has no suitable p because ${\displaystyle N-1=2^{4}}$, and ${\displaystyle p=2<{\sqrt {N}}-1}$, which violates the inequality in (2); other examples include ${\displaystyle N=19,37,41,61,71,73,}$ and ${\displaystyle 97}$.