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 to prove that an integer is prime.
It produces a primality certificate to be found with less effort than the Lucas primality test, which requires the full factorization of .
Pocklington criterion
The basic version of the test relies on the Pocklington theorem (or Pocklington criterion) which is formulated as follows:
Let be an integer, and suppose there exist natural numbers and such that
Then is prime.
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 . With , we find that . This is enough to prove that is not prime.
Suppose is not prime. This means there must be a prime , where that divides .
Since , , and since is prime, .
Thus there must exist an integer , a multiplicative inverse of modulo , with the property that
and therefore, by Fermat's little theorem
This implies
, by () since
, , by () This shows that divides the in (), and therefore this ; a contradiction.
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, has no suitable because , and , which violates the inequality in (); other examples include and .
Given , finding is not nearly as difficult. If is prime, then by Fermat's little theorem, any in the interval will satisfy () (however, the cases and are trivial and will not satisfy ()). This will satisfy () as long as ord() does not divide . Thus a randomly chosen in the interval has a good chance of working. If is a generator mod , its order is and so the method is guaranteed to work for this choice.
Generalized Pocklington test
The above version of version of Pocklington's theorem is sometimes impossible to apply because some primes are such that there is no prime dividing where . The following generalized version of Pocklington's theorem is more widely applicable.
Theorem: Factor as , where and are relatively prime, , the prime factorization of is known, but the factorization of is not necessarily known.
If for each prime factor of there exists an integer so that
then N is prime.
Let be a prime dividing and let be the maximum power of dividing . Let be a prime factor of . For the from the corollary set . This means and because of also .
This means that the order of is
Thus, . The same observation holds for each prime power factor of A, which implies .
Specifically, this means
If were composite, it would necessarily have a prime factor which is less than or equal to . It has been shown that there is no such factor, which proves that is prime.
Comments
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 . Call this product . Then let be the remaining, unfactored portion of . It does not matter whether is prime. We merely need to verify that no prime that divides also divides , that is, that and are relatively prime. Then, for every prime factor of , find an which fulfills conditions () and () of the corollary. If such s can be found, the Corollary implies that is prime.
According to Koblitz, = 2 often works.
Example
Determine whether
is prime.
First, search for small prime factors of . We quickly find that . We must determine whether and meet the conditions of the Corollary. , so . Therefore, we have factored enough of to apply the Corollary. We must also verify that .
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 , try . Raising to this high power can be done efficiently using binary exponentiation:
.
So, satisfies () but not (). As we are allowed a different for each , try instead:
.
So satisfies both () and ().
For , the second prime factor of , try :
. .
satisfies both () and ().