# Pocklington primality test

In mathematics, the Pocklington–Lehmer primality test is a primality test devised by Henry Cabourn Pocklington[1] and Derrick Henry Lehmer.[2] The test uses a partial factorization of ${\displaystyle N-1}$ to prove that an integer ${\displaystyle N}$ is prime.

The output of the test is a proof that ${\displaystyle N}$ is prime, proof that ${\displaystyle N}$ is composite, or that primality could not be established.

## Pocklington criterion

The test relies on the Pocklington Theorem (Pocklington criterion) which is formulated as follows:

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

q is prime, ${\displaystyle q\vert N-1}$ and ${\displaystyle q>{\sqrt {N}}-1}$

(1)

${\displaystyle a^{N-1}\equiv 1{\pmod {N}}}$

(2)

${\displaystyle \gcd {(a^{(N-1)/q}-1,N)}=1}$

(3)

Then N is prime.[3]

### Proof of this theorem

Suppose N is not prime. This means there must be a prime p, where ${\displaystyle p\leq {\sqrt {N}}}$ that divides N.

Therefore, ${\displaystyle q>p-1}$ which implies ${\displaystyle \gcd {(q,p-1)}=1}$.

Thus there must exist an integer u with the property that

${\displaystyle uq\equiv 1{\pmod {p-1}}}$

(4)

This implies:

${\displaystyle 1\;\;\equiv a^{N-1}{\pmod {p}}}$, by (2) since ${\displaystyle p\vert N}$
${\displaystyle \equiv (a^{N-1})^{u}\equiv a^{u(N-1)}\equiv a^{uq((N-1)/q)}\equiv (a^{uq})^{(N-1)/q}{\pmod {p}}}$,
${\displaystyle \equiv a^{(N-1)/q}{\pmod {p}}}$, by (4) and Fermat's little theorem

This shows that p divides ${\displaystyle \gcd()}$ in (3), and therefore this ${\displaystyle \gcd()\neq 1}$; a contradiction.[3]

Given N, if q and a can be found that satisfy the conditions of the theorem, then N is prime. Moreover, the pair (q, a) constitute a Primality certificate. They can be quickly verified to satisfy the conditions of the theorem, confirming N as prime.

The main difficulty is finding a value of q that satisfies (1). First, it is usually difficult to find a large prime factor of a large number. Moreover, for some primes N, such a q does not exist. For example, ${\displaystyle N=17}$ has no suitable q because ${\displaystyle N-1=2^{4}}$, and ${\displaystyle q=2<{\sqrt {N}}-1}$, which violates the inequality in (1). Given q, finding a is not nearly as difficult. [4] If N is prime, then by Fermat's little theorem, any a in the interval ${\displaystyle 1\leq a\leq N-1}$ will satisfy (2) (however, the cases ${\displaystyle a=1}$ and ${\displaystyle a=N-1}$ are trivial and won't satisfy (3)). This a will satisfy (3) as long as ord(a) does not divide ${\displaystyle (N-1)/q}$. Thus a randomly chosen a in the interval ${\displaystyle 2\leq a\leq N-2}$ has a good chance of working. If a is a generator mod N, its order is ${\displaystyle N-1}$ and so the method is guaranteed to work for this choice.

Note: It may happen that, while searching for a value of a that satisfies equation (2), we encounter a value of a such that equation (2) is false. If this occurs (and if a is not divisible by N), then by the Fermat primality test, N is not prime. 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.

## Generalized Pocklington method

There is a generalized version of Pocklington's theorem is more widely applicable because it does not require finding a large prime factor of ${\displaystyle N-1}$; also, it allows a different value of a to be used for each known prime factor of ${\displaystyle N-1}$. [5]:Corollary 1

Corollary:

Factor N − 1 as N − 1 = AB, where A and B are relatively prime, ${\displaystyle A>{\sqrt {N}}}$, the prime factorization of A is known, but the factorization of B is not necessarily known.

If for every prime factor p of A there exists an integer ${\displaystyle a_{p}}$ so that

${\displaystyle a_{p}^{N-1}\equiv 1{\pmod {N}}}$

(5)

and

${\displaystyle \gcd {(a_{p}^{(N-1)/p}-1,N)}=1}$

(6)

,

then N is prime.

Proof of Corollary: Let p be a prime dividing A and let ${\displaystyle p^{e}}$ be the maximum power of p dividing A. Let v be a prime factor of N. For the ${\displaystyle a_{p}}$ from the corollary set ${\displaystyle b\equiv a_{p}^{(N-1)/p^{e}}{\pmod {v}}}$. This means ${\displaystyle b^{p^{e}}\equiv a_{p}^{N-1}\equiv 1{\pmod {v}}}$ and because of ${\displaystyle \gcd {(a_{p}^{(N-1)/p}-1,N)}=1}$ also ${\displaystyle b^{p^{e-1}}\equiv a_{p}^{(N-1)/p}\not \equiv 1{\pmod {v}}}$.

This means that the order of ${\displaystyle b{\pmod {v}}}$ is ${\displaystyle p^{e}}$

Thus, ${\displaystyle p^{e}\vert (v-1)}$. The same observation holds for each prime power factor ${\displaystyle p^{e}}$ of A, which implies ${\displaystyle A\vert (v-1)}$.

Specifically, this means ${\displaystyle v>A\geq {\sqrt {N}}.}$

If N were composite, it would necessarily have a prime factor which is less than or equal to ${\displaystyle {\sqrt {N}}}$. It has been shown that there is no such factor, which proves that N is prime.

## The test

The Pocklington–Lehmer primality test follows directly from this Corollary. To use this Corollary, first find enough factors of N − 1 so the product of those factors exceeds ${\displaystyle {\sqrt {N}}}$. Call this product A. Then let B = (N − 1)/A be the remaining, unfactored portion of N − 1. It does not matter whether B is prime. We merely need to verify that no prime that divides A also divides B, that is, that A and B are relatively prime. Then, for every prime factor p of A, find an ${\displaystyle a_{p}}$ which fulfills conditions (5) and (6) of the Corollary. If such ${\displaystyle a_{p}}$'s can be found, the Corollary implies that N is prime.

According to Koblitz, ${\displaystyle a_{p}}$ = 2 often works.[3]

## Example

Determine whether

${\displaystyle N=27457}$

is prime.

First, search for small prime factors of ${\displaystyle N-1}$. We quickly find that

${\displaystyle N-1=2^{6}\cdot 3\cdot B=192\cdot B}$.

We must determine whether ${\displaystyle A=192}$ and ${\displaystyle B=(N-1)/A=143}$ meet the conditions of the Corollary. ${\displaystyle A^{2}=36864>N}$, so ${\displaystyle A>{\sqrt {N}}}$. Therefore, we have factored enough of ${\displaystyle N-1}$ to apply the Corollary. We must also verify that ${\displaystyle \gcd {(A,B)}=1}$.

It does not matter whether B is prime (in fact, it is not).

Finally, for each prime factor p of A, use trial and error to find an ap that satisfies (5) and (6).

For ${\displaystyle p=2}$, try ${\displaystyle a_{2}=2}$. Raising ${\displaystyle a_{2}}$ to this high power can be done efficiently using binary exponentiation:

${\displaystyle a_{p}^{N-1}\equiv 2^{27456}\equiv 1{\pmod {27457}}}$
${\displaystyle \gcd {(a_{p}^{(N-1)/p}-1,N)}=\gcd {(2^{13728}-1,27457)}=27457}$.

So, ${\displaystyle a_{2}=2}$ satisfies (5) but not (6). The Corollary is quite versatile, and allows different ap for each p. Trying ${\displaystyle a_{2}=5}$, we find

${\displaystyle a_{p}^{N-1}\equiv 2^{27456}\equiv 1{\pmod {27457}}}$
${\displaystyle \gcd {(a_{p}^{(N-1)/p}-1,N)}=\gcd {(5^{13728}-1,27457)}=1}$.

So ${\displaystyle a_{2}=5}$ satisfies both (5) and (6).

For ${\displaystyle p=3}$, the second prime factor of A, try ${\displaystyle a_{3}=2}$:

${\displaystyle a_{p}^{N-1}\equiv 3^{27456}\equiv 1{\pmod {27457}}}$.
${\displaystyle \gcd {(a_{p}^{(N-1)/p}-1,N)}=\gcd {(2^{9152}-1,27457)}=1}$.

${\displaystyle a_{3}=2}$ satisfies both (5) and (6).

According to the Corollary, this completes the proof that ${\displaystyle N=27457}$ is prime. The certificate of primality for ${\displaystyle N=27457}$ would consist of the two ${\displaystyle (p,a_{p})}$ pairs (2, 5) and (3, 2).

We have chosen a small prime for calculation purposes but in practice when we start factoring A we may get factors that themselves must be checked for primality. We cannot prove N is prime until we know the factors of A are prime as well. If we get a factor of A where primality is not certain, a test must also be performed on this factor. 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 example, we can say with certainty that 2 and 3 are prime, and thus we have proved our result. The primality certificate is the list of ${\displaystyle (p,a_{p})}$pairs, which can be quickly 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 ap'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 ap'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 point is that a certificate can be produced, containing at each level the prime to be tested, and the corresponding ap's, which can easily be verified.

## Extensions and variants

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. This includes their Theorem 3 (a strengthening of an 1878 theorem of Proth):

Let ${\displaystyle N-1=mp}$ where p is an odd prime such that ${\displaystyle 2p+1>{\sqrt {N}}}$. If there exists an a for which ${\displaystyle a^{(N-1)/2}\equiv -1{\pmod {N}}}$, but ${\displaystyle a^{m/2}\not \equiv -1{\pmod {N}}}$, then N is prime.

If N is large, it is often difficult to factor enough of ${\displaystyle N-1}$ to apply the above corollary. Theorem 5 of the Brillhart, Lehmer, and Selfridge paper allows a primality proof when the factored part has reached only ${\displaystyle (N/2)^{1/3}}$. Many additional such theorems are presented that allow one to prove the primality of N based on the partial factorization of ${\displaystyle N-1}$ and ${\displaystyle N+1}$.

## References

1. ^ H. C. Pocklington (1914–1916). "The determination of the prime or composite nature of large numbers by Fermat's theorem". Proceedings of the Cambridge Philosophical Society. 18: 29–30.
2. ^ D. H. Lehmer (1927). "Tests for primality by the converse of Fermat's theorem". Bull. Amer. Math. Soc. 33 (3): 327–340. doi:10.1090/s0002-9904-1927-04368-3.
3. ^ a b c Koblitz, Neal, A Course in Number Theory and Cryptography, 2nd Ed, Springer,1994
4. ^ Roberto Avanzi, Henri Cohen, Christophe Doche, Gerhard Frey, Tanja Lange, Kim Nguyen, Frederik Vercauteren (2005). Handbook of Elliptic and Hyperelliptic Curve Cryptography. Boca Raton: Chapman & Hall/CRC.
5. ^ a b John Brillhart; D. H. Lehmer; J. L. Selfridge (April 1975). "New Primality Criteria and Factorizations of 2m ± 1". Mathematics of Computation. 29 (130): 620–647. doi:10.1090/S0025-5718-1975-0384673-1. JSTOR 2005583.