In mathematics, the Pocklington–Lehmer primality test is a primality test devised by Henry Cabourn Pocklington and Derrick Henry Lehmer to decide whether a given number
Contents
Pocklington criterion
The test relies on the Pocklington Theorem (Pocklington criterion) which is formulated as follows:
Let
Then N is prime.
Proof of this theorem
Suppose N is not prime. This means there must be a prime p, where
Therefore,
Thus there must exist an integer u with the property that
This implies:
This shows that p divides
The test is simple once the theorem above is established. Given N, seek to find suitable a and q. If they can be obtained, then N is prime. Moreover, a and q are the certificate of primality. They can be quickly verified to satisfy the conditions of the theorem, confirming N as prime.
A problem which arises is the ability to find a suitable q, that must satisfy (1)–(3) and be provably prime. It is even quite possible that such a q does not exist. This is a large probability, indeed only 57.8% of the odd primes, N,
Generalized Pocklington method
A generalized version of Pocklington's theorem covers more primes N.
Corollary:
Let N − 1 factor as N − 1 = AB, where A and B are relatively prime,
If for every prime factor p of A there exists an integer
and
Proof of Corollary: Let p be a prime dividing A and let
This means that the order of
Thus,
Specifically, this means
If N were composite, it would necessarily have a prime factor which is less than or equal to
To see the converse choose
The test
The Pocklington–Lehmer primality test follows directly from this corollary. We must first partially factor N − 1 into A and B. Then we must find an
According to Koblitz,
Example
Choose
Now it is clear that
Next find an
So
and
So both
We have chosen a small prime for calculation purposes but in practice when we start factoring A we will get factors that themselves must be checked for primality. It is not a proof of primality until we know our factors of A are prime as well. If we get a factor of A where primality is not certain, the test must be performed on this factor as well. 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 case, we can say with certainty that 2, 5, and 227 are prime, and thus we have proved our result. The certificate in our case is the list of
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
The biggest difficulty with this test is the necessity of discovering prime factors of N - 1, in essence, factoring N − 1. In practice this could be extremely difficult. Finding
Extensions and variants
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 allowing less factoring. This includes theorem 3 (a strengthening of Proth 1878):
Letand theorem 5 on page 624 that allows a proof when the factored part has reached only