View source for Pocklington primality test

{{Short description|Number-theoretic algorithm}}
In mathematics, the '''Pocklington&ndash;Lehmer primality test''' is a [[primality test]] devised by [[Henry Cabourn Pocklington]]<ref name="Pocklington">{{cite journal|first=Henry C. |last=Pocklington |author-link=Henry Cabourn Pocklington |title=The determination of the prime or composite nature of large numbers by Fermat's theorem|journal=Proceedings of the Cambridge Philosophical Society|volume=18|date=1914–1916|pages=29–30|url=https://archive.org/details/proceedingsofcam1718191316camb/page/28/mode/2up|access-date=2022-06-22}}</ref> and [[Derrick Henry Lehmer]].<ref name="Lehmer">{{cite journal|author=D. H. Lehmer |author-link=Derrick Henry Lehmer |title=Tests for primality by the converse of Fermat's theorem |journal=Bull. Amer. Math. Soc. |volume=33|number=3|date=1927|pages=327–340 |url=https://projecteuclid.org/euclid.bams/1183492108|doi=10.1090/s0002-9904-1927-04368-3|doi-access=free}}</ref>
The test uses a partial factorization of <math>N - 1</math> to prove that an integer <math>N</math> is [[Prime number|prime]].

It produces a [[primality certificate]] to be found with less effort than the [[Lucas primality test]], which requires the full factorization of <math>N - 1</math>.

==Pocklington criterion==
The basic version of the test relies on the '''Pocklington theorem''' (or '''Pocklington criterion''') which is formulated as follows:

Let <math>N > 1</math> be an integer, and suppose there exist natural numbers {{mvar|a}} and {{mvar|p}} such that

{{NumBlk|:|<math>a^{N-1} \equiv 1 \pmod{N}</math>|{{EquationRef|1}}}}
{{NumBlk|:|{{mvar|p}} is prime, <math>p \vert N - 1</math> and <math>p > \sqrt{N} - 1</math>|{{EquationRef|2}}}}
{{NumBlk|:|<math>\gcd{(a^{(N-1)/p} - 1, N)} = 1</math>|{{EquationRef|3}}}}

Then {{mvar|N}} is prime.<ref name="koblitz">{{cite book |last=Koblitz |first=Neal |author-link=Neal Koblitz |title=A Course in Number Theory and Cryptography |edition=2nd |publisher=Springer |year=1994 |series=Graduate Texts in Mathematics |volume=144 |isbn=0-387-94293-9}}</ref> Here <math>i \equiv j \pmod{k}</math> means that after finding the remainder of division by ''k'', ''i'' and ''j'' are equal; <math>i \vert j</math> means that ''i'' is a [[divisor]] for ''j''; and gcd is the [[greatest common divisor]]. 

Note: Equation ({{EquationNote|1}}) is simply a [[Fermat primality test]].  If we find ''any'' value of {{mvar|a}}, not divisible by {{mvar|N}}, such that equation ({{EquationNote|1}}) is false, we may immediately conclude that {{mvar|N}} is not prime.  (This divisibility condition is not explicitly stated because it is implied by equation ({{EquationNote|3}}).)  For example, let <math>N = 35</math>. With <math>a = 2</math>, we find that <math>a^{N-1} \equiv 9 \pmod{N}</math>.  This is enough to prove that {{mvar|N}} is not prime.

{{collapse top|title=Proof}}
Suppose {{mvar|N}} is not prime.  This means there must be a prime {{mvar|q}}, where <math>q \le \sqrt{N}</math> that divides {{mvar|N}}.

Since <math>p > \sqrt N - 1 \ge q - 1</math>, <math>p > q - 1</math>, and since {{mvar|p}} is prime, <math>\gcd{(p, q - 1)} = 1</math>.

Thus there must exist an integer {{mvar|u}}, a multiplicative inverse of {{mvar|p}} modulo {{math|''q''−1}}, with the property that

{{NumBlk|:|<math> up\equiv 1 \pmod{q - 1}</math>|{{EquationRef|4}}}}

and therefore, by [[Fermat's little theorem]]

{{NumBlk|:|<math>a^{up}\equiv a \pmod q</math>|{{EquationRef|5}}}}

This implies
 
:   <math>1 \;\; \equiv a^{N-1}\pmod{q}</math>, {{quad}}by '''({{EquationNote|1}})''' since <math>q \vert N </math>
::   <math>\equiv (a^{N-1})^{u}\equiv a^{u(N-1)} \equiv a^{up((N-1)/p)}\equiv (a^{up})^{(N-1)/p}\pmod{q}</math>,
::   <math>\equiv a^{(N-1)/p}\pmod{q}</math>, {{quad}}by '''({{EquationNote|5}})'''
This shows that {{mvar|q}} divides the <math>\gcd()</math> in '''({{EquationNote|3}})''', and therefore this <math>\gcd() \ne 1</math>; a contradiction.<ref name="koblitz" />
{{collapse bottom}}

Given {{mvar|N}}, if {{mvar|p}} and {{mvar|a}} can be found which satisfy the conditions of the theorem, then {{mvar|N}} is prime.  Moreover, the pair ({{mvar|p}}, {{mvar|a}}) constitute a ''primality certificate'' which can be quickly verified to satisfy the conditions of the theorem, confirming {{mvar|N}} as prime.

The main difficulty is finding a value of {{mvar|p}} which satisfies ({{EquationNote|2}}).  First, it is usually difficult to find a large prime factor of a large number.  Second, for many primes {{mvar|N}}, such a {{mvar|p}} does not exist. For example, <math>N = 17</math> has no suitable {{mvar|p}} because <math>N - 1 = 2^4</math>, and <math>p = 2 < \sqrt{N}-1</math>, which violates the inequality in '''({{EquationNote|2}})'''; other examples include
<math>N = 19, 37, 41, 61, 71, 73,</math> and <math>97</math>.

Given {{mvar|p}}, finding {{mvar|a}} is not nearly as difficult.<ref>{{cite book|author=Roberto Avanzi |author2=Henri Cohen |author3=Christophe Doche |author4=Gerhard Frey |author5=[[Tanja Lange]] |author6=Kim Nguyen |author7=Frederik Vercauteren |title=Handbook of Elliptic and Hyperelliptic Curve Cryptography |publisher=Chapman & Hall/CRC |location=Boca Raton |year=2005 |url=http://www.hyperelliptic.org/HEHCC}}</ref>  If {{mvar|N}} is prime, then by Fermat's little theorem, any {{mvar|a}} in the interval <math>1 \leq a \leq N - 1</math> will satisfy ({{EquationNote|1}}) (however, the cases <math>a = 1</math> and <math>a = N - 1</math> are trivial and will not satisfy ({{EquationNote|3}})). This {{mvar|a}} will satisfy ({{EquationNote|3}}) as long as [[Order (group theory)|ord({{mvar|a}})]] does not divide <math>(N - 1)/p</math>.  Thus a randomly chosen {{mvar|a}} in the interval <math>2 \leq a \leq N - 2</math> has a good chance of working. If {{mvar|a}} is a generator mod {{mvar|N}}, its order is {{tmath|N-1}} and so the method is guaranteed to work for this choice.

==Generalized Pocklington test==
The above version of Pocklington's theorem is sometimes impossible to apply because some primes <math>N</math> are such that there is no prime <math>p</math> dividing <math>N - 1</math> where <math>p > \sqrt{N} - 1</math>. The following generalized version of Pocklington's theorem is more widely applicable.<ref name="BLS75">{{cite journal |first1=John |last1=Brillhart |author-link1=John Brillhart |first2=D. H. |last2=Lehmer |author-link2=Derrick Henry Lehmer |first3=J. L. |last3=Selfridge |author-link3=John Selfridge |title=New Primality Criteria and Factorizations of 2<sup>m</sup> ± 1 |journal=Mathematics of Computation |volume=29 |number=130 |date=April 1975 |pages=620–647 |jstor=2005583 |doi=10.1090/S0025-5718-1975-0384673-1 |url=https://www.ams.org/journals/mcom/1975-29-130/S0025-5718-1975-0384673-1/S0025-5718-1975-0384673-1.pdf|doi-access=free }}</ref>{{rp|Corollary 1}}

'''Theorem:''' Factor {{math|''N''&nbsp;&minus;&nbsp;1}} as {{math|1=''N''&nbsp;&minus;&nbsp;1 =&nbsp;''AB''}}, where {{mvar|A}} and {{mvar|B}} are relatively prime, <math>A > \sqrt{N}</math>, the prime factorization of {{mvar|A}} is known, but the factorization of {{mvar|B}} is not necessarily known.

If for each prime factor {{mvar|p}} of {{mvar|A}} there exists an integer <math>a_p</math> so that

{{NumBlk|:|<math>a_p^{N - 1}\equiv 1 \pmod{N}</math>, and|{{EquationRef|6}}}}
{{NumBlk|:|<math>\gcd{(a_p^{(N - 1)/p} - 1, N)} = 1</math>,|{{EquationRef|7}}}}
then ''N'' is prime.

{{collapse top|title=Proof}}
Let {{mvar|p}} be a prime dividing {{mvar|A}} and let <math>p^e</math> be the maximum power of {{mvar|p}} dividing {{mvar|A}}.
Let {{mvar|q}} be a prime factor of {{mvar|N}}. For the <math>a_p</math> from the corollary set
<math>b \equiv a_p^{(N-1)/p^e} \pmod{q}</math>. This means
<math>b^{p^e} \equiv a_p^{N-1} \equiv 1 \pmod{q}</math>  and because of <math>\gcd{(a_p^{(N-1)/p} - 1, N)} = 1</math> also
<math>b^{p^{e-1}} \equiv a_p^{(N-1)/p} \not\equiv 1 \pmod{q}</math>.

This means that the order of <math>b \pmod{q}</math> is <math>p^e</math>

Thus, <math>p^e \vert (q - 1)</math>.  The same observation holds for each prime power factor <math>p^e</math> of ''A'',
which implies <math>A \vert (q - 1)</math>.

Specifically, this means <math>q > A \ge \sqrt{N}.</math>

If {{mvar|N}} were composite, it would necessarily have a prime factor which is less than or equal to <math>\sqrt{N}</math>.  It has been shown that there is no such factor, which proves that {{mvar|N}} is prime.
{{collapsed bottom}}

===Comments===
The Pocklington–Lehmer primality test follows directly from this corollary.
<!-- We first partially factor ''N''&nbsp;&minus;&nbsp;1 into {{mvar|A}} and {{mvar|B}}. -->
To use this corollary, first find enough factors of {{math|''N''&nbsp;&minus;&nbsp;1}} so the product of those factors exceeds <math>\sqrt{N}</math>.
Call this product {{mvar|A}}.
Then let {{math|1=''B'' = (''N''&nbsp;&minus;&nbsp;1)/''A''}} be the remaining, unfactored portion of {{math|''N''&nbsp;&minus;&nbsp;1}}. It does not matter whether {{mvar|B}} is prime.
We merely need to verify that no prime that divides {{mvar|A}} also divides {{mvar|B}}, that is, that {{mvar|A}} and {{mvar|B}} are relatively prime.
Then, for every prime factor {{mvar|p}} of {{mvar|A}}, find an <math>a_p</math> which fulfills conditions '''({{EquationNote|6}})''' and '''({{EquationNote|7}})''' of the corollary.
If such <math>a_p</math>s can be found, the Corollary implies that {{mvar|N}} is prime.

According to Koblitz, <math>a_p</math> = 2 often works.<ref name="koblitz" />

===Example===

Determine whether
: <math>N = 27457</math>
is prime.

First, search for small prime factors of <math>N - 1</math>.
We quickly find that
: <math>N - 1 = 2^6 \cdot 3 \cdot B = 192 \cdot B</math>.
We must determine whether <math>A = 192</math> and <math>B = (N - 1)/A = 143</math> meet the conditions of the Corollary.
<math>A^2 = 36864 > N</math>, so <math>A > \sqrt{N}</math>.
Therefore, we have factored enough of <math>N - 1</math> to apply the Corollary.
We must also verify that <math>\gcd{(A, B)} = 1</math>.

It does not matter whether {{mvar|B}} is prime (in fact, it is not).

Finally, for each prime factor {{mvar|p}} of {{mvar|A}}, use trial and error to find an {{mvar|a{{sub|p}}}} that satisfies '''({{EquationNote|6}})''' and '''({{EquationNote|7}})'''.

For <math>p = 2</math>, try <math>a_2 = 2</math>.
Raising <math>a_2</math> to this high power can be done efficiently using [[Modular exponentiation#Left-to-right binary method|binary exponentiation]]:

: <math>a_2^{N - 1} \equiv 2^{27456} \equiv 1 \pmod{27457}</math>
: <math>\gcd{(a_2^{(N - 1)/2} - 1, N)} = \gcd{(2^{13728} - 1, 27457)} = 27457</math>.

So, <math>a_2 = 2</math> satisfies '''({{EquationNote|6}})''' but not '''({{EquationNote|7}})'''.  As we are allowed a different {{mvar|a{{sub|p}}}} for each {{mvar|p}}, try <math>a_2 = 5</math> instead:

: <math>a_2^{N - 1} \equiv 5^{27456} \equiv 1 \pmod{27457}</math>
: <math>\gcd{(a_2^{(N - 1)/2} - 1, N)} = \gcd{(5^{13728} - 1, 27457)} = 1</math>.

So <math>a_2 = 5</math> satisfies both '''({{EquationNote|6}})''' and '''({{EquationNote|7}})'''.

For <math>p = 3</math>, the second prime factor of {{mvar|A}}, try <math>a_3 = 2</math>:

: <math>a_3^{N - 1} \equiv 2^{27456} \equiv 1 \pmod{27457}</math>.
: <math>\gcd{(a_3^{(N - 1)/3} - 1, N)} = \gcd{(2^{9152} - 1, 27457)} = 1</math>.

<math>a_3 = 2</math> satisfies both '''({{EquationNote|6}})''' and '''({{EquationNote|7}})'''.

This completes the proof that <math>N = 27457</math> is prime.
The certificate of primality for <math>N = 27457</math> would consist of the two <math>(p, a_p)</math> pairs (2, 5) and (3, 2).

We have chosen small numbers for this example, but in practice when we start factoring {{mvar|A}} we may get factors that are themselves so large their primality is not obvious.  We cannot prove {{mvar|N}} is prime without proving that the factors of {{mvar|A}} are prime as well.  In such a case we use the same test recursively on the large factors of {{mvar|A}}, 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 <math>(p, a_p)</math>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 {{mvar|a{{sub|p}}}}s which correspond to the 'prime' factors of {{mvar|A}}; Next, for each factor of {{mvar|A}} where primality was uncertain, we would have more {{mvar|a{{sub|p}}}}, 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 {{mvar|a{{sub|p}}}}s, which can easily be verified.

==Extensions and variants==

The 1975 paper by Brillhart, Lehmer, and Selfridge<ref name="BLS75" /> 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 <math>N-1 = mp</math> where {{mvar|p}} is an odd prime such that <math>2p+1 > \sqrt N</math>.  If there exists an {{mvar|a}} for which <math>a^{(N-1)/2} \equiv -1 \pmod{N}</math>, but <math>a^{m/2} \not\equiv -1 \pmod{N}</math>, then {{mvar|N}} is prime.

If {{mvar|N}} is large, it is often difficult to factor enough of <math>N - 1</math> 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 <math>(N/2)^{1/3}</math>.  Many additional such theorems are presented that allow one to prove the primality of {{mvar|N}} based on the partial factorization of <math>N - 1</math>, <math>N + 1</math>, <math>N^2 + 1</math>, and <math>N^2 \pm N + 1</math>.<ref name="BLS75" /><ref>{{cite journal | first1=Hugh C. | last1=Williams |first2=R. |last2=Holte| title =  Some observations on primality testing | journal = Mathematics of Computation | date = July 1978 | volume = 32 |issue = 143 | pages = 905–917 |jstor=2006495 |doi=10.2307/2006495 |doi-access=free}}</ref><ref>[https://primes.utm.edu/prove/prove3.html The classical tests]</ref>

== 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".)
{{Reflist}}

== External links ==
*Chris Caldwell, [https://primes.utm.edu/prove/prove3_1.html "Primality Proving 3.1: n-1 tests and the Pepin's tests for Fermats"] at the [[Prime Pages]].
*Chris Caldwell, [https://primes.utm.edu/prove/prove3_2.html "Primality Proving 3.2: n+1 tests and the Lucas-Lehmer test for Mersennes"] at the [[Prime Pages]].

{{Number-theoretic algorithms}}

{{DEFAULTSORT:Pocklington Primality Test}}
[[Category:Primality tests]]