Pocklington primality test
Introduction 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 thatThen  is prime. Here  means that after finding the remainder of division by ''k'', ''i'' and ''j'' are equal;  means that ''i'' is a divisor for ''j''; and gcd is the greatest common divisor. 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 thatand therefore, by Fermat's little theoremThis 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 thatthen ''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 '''()'''.This completes the proof that  is prime.The certificate of primality for  would consist of the two  pairs (2, 5) and (3, 2).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 pairs, which can be quickly checked in the corollary.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.
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 which allow less factoring. This includes their Theorem 3 (a strengthening of an 1878 theorem of Proth):: Let  where  is an odd prime such that . If there exists an  for which , but , then  is prime.If  is large, it is often difficult to factor enough of  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 . Many additional such theorems are presented that allow one to prove the primality of  based on the partial factorization of , , , and .
References * Leonard Eugene Dickson, "History of the Theory of Numbers" vol 1, p 370, Chelsea Publishing 1952* Henry Pocklington, "Math. Quest. Educat. Times", (2), 25, 1914, p 43-46 (Mathematical questions and solutions in continuation of the mathematical columns of "the Educational times".)
External links *Chris Caldwell,  "Primality Proving 3.1: n-1 tests and the Pepin's tests for Fermats" at the Prime Pages. *Chris Caldwell,  "Primality Proving 3.2: n+1 tests and the Lucas-Lehmer test for Mersennes" at the Prime Pages.