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
N-1
N
It produces a primality certificate to be found with less effort than the Lucas primality test, which requires the full factorization of
N-1
The basic version of the test relies on the Pocklington theorem (or Pocklington criterion) which is formulated as follows:
Let
N>1
Then is prime.[3] Here
i\equivj\pmod{k}
i\vertj
Note: Equation is simply a Fermat primality test. If we find any value of, not divisible by, such that equation is false, we may immediately conclude that is not prime. (This divisibility condition is not explicitly stated because it is implied by equation .) For example, let
N=35
a=2
aN-1\equiv9\pmod{N}
Suppose is not prime. This means there must be a prime, where
q\le\sqrt{N}
Since
p>\sqrtN-1\geq-1
p>q-1
\gcd{(p,q-1)}=1
Thus there must exist an integer, a multiplicative inverse of modulo, with the property that
and therefore, by Fermat's little theorem
This implies
1 \equivaN-1\pmod{q}
q\vertN
\equiv(aN-1)u\equivau(N-1)\equivaup((N-1)/p)\equiv(aup)(N-1)/p\pmod{q}
\equiva(N-1)/p\pmod{q}
\gcd
\gcd\ne1
Given, if and can be found which satisfy the conditions of the theorem, then is prime. Moreover, the pair constitute a primality certificate which can be quickly verified to satisfy the conditions of the theorem, confirming as prime.
The main difficulty is finding a value of which satisfies . First, it is usually difficult to find a large prime factor of a large number. Second, for many primes, such a does not exist. For example,
N=17
N-1=24
p=2<\sqrt{N}-1
N=19,37,41,61,71,73,
97
Given, finding is not nearly as difficult.[4] If is prime, then by Fermat's little theorem, any in the interval
1\leqa\leqN-1
a=1
a=N-1
(N-1)/p
2\leqa\leqN-2
The above version of Pocklington's theorem is sometimes impossible to apply because some primes
N
p
N-1
p>\sqrt{N}-1
Theorem: Factor as, where and are relatively prime,
A>\sqrt{N}
If for each prime factor of there exists an integer
ap
then N is prime.
Let be a prime dividing and let
pe
ap
b\equiv
| (N-1)/pe | |
| a | |
| p |
\pmod{q}
| pe | |
| b |
\equiv
| N-1 | |
| a | |
| p |
\equiv1\pmod{q}
| (N-1)/p | |
| \gcd{(a | |
| p |
-1,N)}=1
| pe-1 | |
| b |
\equiv
| (N-1)/p | |
| a | |
| p |
\not\equiv1\pmod{q}
This means that the order of
b\pmod{q}
pe
Thus,
pe\vert(q-1)
pe
A\vert(q-1)
Specifically, this means
q>A\ge\sqrt{N}.
If were composite, it would necessarily have a prime factor which is less than or equal to
\sqrt{N}
The Pocklington–Lehmer primality test follows directly from this corollary.To use this corollary, first find enough factors of so the product of those factors exceeds
\sqrt{N}
ap
ap
According to Koblitz,
ap
Determine whether
N=27457
First, search for small prime factors of
N-1
N-1=26 ⋅ 3 ⋅ B=192 ⋅ B
A=192
B=(N-1)/A=143
A2=36864>N
A>\sqrt{N}
N-1
\gcd{(A,B)}=1
It does not matter whether is prime (in fact, it is not).
Finally, for each prime factor of, use trial and error to find an that satisfies and .
For
p=2
a2=2
a2
| N-1 | |
| a | |
| 2 |
\equiv227456\equiv1\pmod{27457}
| (N-1)/2 | |
| \gcd{(a | |
| 2 |
-1,N)}=\gcd{(213728-1,27457)}=27457
So,
a2=2
a2=5
| N-1 | |
| a | |
| 2 |
\equiv527456\equiv1\pmod{27457}
| (N-1)/2 | |
| \gcd{(a | |
| 2 |
-1,N)}=\gcd{(513728-1,27457)}=1
So
a2=5
For
p=3
a3=2
| N-1 | |
| a | |
| 3 |
\equiv227456\equiv1\pmod{27457}
| (N-1)/3 | |
| \gcd{(a | |
| 3 |
-1,N)}=\gcd{(29152-1,27457)}=1
a3=2
This completes the proof that
N=27457
N=27457
(p,ap)
We have chosen small numbers for this example, but in practice when we start factoring we may get factors that are themselves so large their primality is not obvious. We cannot prove is prime without proving that the factors of are prime as well. In such a case we use the same test recursively on the large factors of, 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. The primality certificate is the list of
(p,ap)
If our example had included large prime factors, the certificate would be more complicated. It would first consist of our initial round of s which correspond to the 'prime' factors of ; Next, for each factor of where primality was uncertain, we would have more, 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 s, which can easily be verified.
The 1975 paper by Brillhart, Lehmer, and Selfridge 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
N-1=mp
2p+1>\sqrtN
a(N-1)/2\equiv-1\pmod{N}
am/2\not\equiv-1\pmod{N}
If is large, it is often difficult to factor enough of
N-1
(N/2)1/3
N-1
N+1
N2+1
N2\pmN+1