Pocklington primality test

Template:Short description 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 $N-1$ to prove that an integer $N$ is prime.

It produces a primality certificate to be found with less effort than the Lucas primality test, which requires the full factorization of $N-1$.

Pocklington criterion

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

Let $N>1$ be an integer, and suppose there exist natural numbers Template:Mvar and Template:Mvar such that

Then Template:Mvar is prime. Here $i\equiv j(\mathrm{mod}k)$ means that after finding the remainder of division by k, i and j are equal; $i|j$ means that i is a divisor for j; and gcd is the greatest common divisor.

Note: Equation (Template:EquationNote) is simply a Fermat primality test. If we find any value of Template:Mvar, not divisible by Template:Mvar, such that equation (Template:EquationNote) is false, we may immediately conclude that Template:Mvar is not prime. (This divisibility condition is not explicitly stated because it is implied by equation (Template:EquationNote).) For example, let $N=35$. With $a=2$, we find that $a^{N-1}\equiv 9(\mathrm{mod}N)$. This is enough to prove that Template:Mvar is not prime.

Template:Collapse top Suppose Template:Mvar is not prime. This means there must be a prime Template:Mvar, where $q\le \sqrt{N}$ that divides Template:Mvar.

Since $p>\sqrt{N}-1\ge q-1$, $p>q-1$, and since Template:Mvar is prime, $\gcd (p,q-1)=1$.

Thus there must exist an integer Template:Mvar, a multiplicative inverse of Template:Mvar modulo Template:Math, with the property that

and therefore, by Fermat's little theorem

This implies

$1\equiv a^{N-1}(\mathrm{mod}q)$, Template:Quadby (Template:EquationNote) since $q|N$

$\equiv (a^{N-1}{)}^u\equiv a^{u(N-1)}\equiv a^{up((N-1)/p)}\equiv (a^{up}{)}^{(N-1)/p}(\mathrm{mod}q)$,

$\equiv a^{(N-1)/p}(\mathrm{mod}q)$, Template:Quadby (Template:EquationNote)

This shows that Template:Mvar divides the $\gcd ()$ in (Template:EquationNote), and therefore this $\gcd ()\ne 1$; a contradiction. Template:Collapse bottom

Given Template:Mvar, if Template:Mvar and Template:Mvar can be found which satisfy the conditions of the theorem, then Template:Mvar is prime. Moreover, the pair (Template:Mvar, Template:Mvar) constitute a primality certificate which can be quickly verified to satisfy the conditions of the theorem, confirming Template:Mvar as prime.

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

Given Template:Mvar, finding Template:Mvar is not nearly as difficult. If Template:Mvar is prime, then by Fermat's little theorem, any Template:Mvar in the interval $1\le a\le N-1$ will satisfy (Template:EquationNote) (however, the cases $a=1$ and $a=N-1$ are trivial and will not satisfy (Template:EquationNote)). This Template:Mvar will satisfy (Template:EquationNote) as long as [[Order (group theory)|ord(Template:Mvar)]] does not divide $(N-1)/p$. Thus a randomly chosen Template:Mvar in the interval $2\le a\le N-2$ has a good chance of working. If Template:Mvar is a generator mod Template:Mvar, its order is Template:Tmath 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 $N$ are such that there is no prime $p$ dividing $N-1$ where $p>\sqrt{N}-1$. The following generalized version of Pocklington's theorem is more widely applicable.Template:Rp

Theorem: Factor Template:Math as Template:Math, where Template:Mvar and Template:Mvar are relatively prime, $A>\sqrt{N}$, the prime factorization of Template:Mvar is known, but the factorization of Template:Mvar is not necessarily known.

If for each prime factor Template:Mvar of Template:Mvar there exists an integer $a_p$ so that

Template:NumBlk Template:NumBlk then N is prime.

Template:Collapse top Let Template:Mvar be a prime dividing Template:Mvar and let $p^e$ be the maximum power of Template:Mvar dividing Template:Mvar. Let Template:Mvar be a prime factor of Template:Mvar. For the $a_p$ from the corollary set $b\equiv a_p^{(N-1)/p^e}(\mathrm{mod}q)$. This means $b^{p^e}\equiv a_p^{N-1}\equiv 1(\mathrm{mod}q)$ and because of $\gcd (a_p^{(N-1)/p}-1,N)=1$ also $b^{p^{e-1}}\equiv a_p^{(N-1)/p}\equiv ̸1(\mathrm{mod}q)$.

This means that the order of $b(\mathrm{mod}q)$ is $p^e$

Thus, $p^e|(q-1)$. The same observation holds for each prime power factor $p^e$ of A, which implies $A|(q-1)$.

Specifically, this means $q>A\ge \sqrt{N}.$

If Template:Mvar were composite, it would necessarily have a prime factor which is less than or equal to $\sqrt{N}$. It has been shown that there is no such factor, which proves that Template:Mvar is prime. Template:Collapsed bottom

Comments

The Pocklington–Lehmer primality test follows directly from this corollary. To use this corollary, first find enough factors of Template:Math so the product of those factors exceeds $\sqrt{N}$. Call this product Template:Mvar. Then let Template:Math be the remaining, unfactored portion of Template:Math. It does not matter whether Template:Mvar is prime. We merely need to verify that no prime that divides Template:Mvar also divides Template:Mvar, that is, that Template:Mvar and Template:Mvar are relatively prime. Then, for every prime factor Template:Mvar of Template:Mvar, find an $a_p$ which fulfills conditions (Template:EquationNote) and (Template:EquationNote) of the corollary. If such $a_p$s can be found, the Corollary implies that Template:Mvar is prime.

According to Koblitz, $a_p$ = 2 often works.

Example

Determine whether

$N=27457$

is prime.

First, search for small prime factors of $N-1$. We quickly find that

$N-1=2^6\cdot 3\cdot B=192\cdot B$.

We must determine whether $A=192$ and $B=(N-1)/A=143$ meet the conditions of the Corollary. $A^2=36864>N$, so $A>\sqrt{N}$. Therefore, we have factored enough of $N-1$ to apply the Corollary. We must also verify that $\gcd (A,B)=1$.

It does not matter whether Template:Mvar is prime (in fact, it is not).

Finally, for each prime factor Template:Mvar of Template:Mvar, use trial and error to find an Template:Mvar that satisfies (Template:EquationNote) and (Template:EquationNote).

For $p=2$, try $a_2=2$. Raising $a_2$ to this high power can be done efficiently using binary exponentiation:

$a_2^{N-1}\equiv 2^{27456}\equiv 1(\mathrm{mod}27457)$

$\gcd (a_2^{(N-1)/2}-1,N)=\gcd (2^{13728}-1,27457)=27457$.

So, $a_2=2$ satisfies (Template:EquationNote) but not (Template:EquationNote). As we are allowed a different Template:Mvar for each Template:Mvar, try $a_2=5$ instead:

$a_2^{N-1}\equiv 5^{27456}\equiv 1(\mathrm{mod}27457)$

$\gcd (a_2^{(N-1)/2}-1,N)=\gcd (5^{13728}-1,27457)=1$.

So $a_2=5$ satisfies both (Template:EquationNote) and (Template:EquationNote).

For $p=3$, the second prime factor of Template:Mvar, try $a_3=2$:

$a_3^{N-1}\equiv 2^{27456}\equiv 1(\mathrm{mod}27457)$.

$\gcd (a_3^{(N-1)/3}-1,N)=\gcd (2^{9152}-1,27457)=1$.

$a_3=2$ satisfies both (Template:EquationNote) and (Template:EquationNote).

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

We have chosen small numbers for this example, but in practice when we start factoring Template:Mvar we may get factors that are themselves so large their primality is not obvious. We cannot prove Template:Mvar is prime without proving that the factors of Template:Mvar are prime as well. In such a case we use the same test recursively on the large factors of Template:Mvar, 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,a_p)$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 Template:Mvars which correspond to the 'prime' factors of Template:Mvar; Next, for each factor of Template:Mvar where primality was uncertain, we would have more Template:Mvar, 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 Template:Mvars, 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 $N-1=mp$ where Template:Mvar is an odd prime such that $2p+1>\sqrt{N}$. If there exists an Template:Mvar for which $a^{(N-1)/2}\equiv -1(\mathrm{mod}N)$, but $a^{m/2}\equiv ̸-1(\mathrm{mod}N)$, then Template:Mvar is prime.

If Template:Mvar is large, it is often difficult to factor enough of $N-1$ 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 $(N/2{)}^{1/3}$. Many additional such theorems are presented that allow one to prove the primality of Template:Mvar based on the partial factorization of $N-1$, $N+1$, $N^2+1$, and $N^2\pm N+1$.

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.