## Pocklington’s N-1 Primality Prover

### September 28, 2012

In previous exercises we have seen two methods for determining if a number is probably prime, the Miller-Rabin and Baillie-Wagstaff methods, and two methods for proving a number prime, trial division and the Lucas N-1 prover, which requires the complete factorization of *n*−1, where *n* is the number to be proved prime. In today’s exercise we examine a method of Pocklington in which a number can be proved prime with only a partial factorization of *n*−1.

We begin by expressing the number to be proved prime as *n* = *f* · *r* + 1, where the complete factorization of *f* is known and exceeds the square root of *n*. Pocklington proved that if, for some *a*, *a*^{n−1} ≡ 1 (mod *n*) and gcd(*a*^{(n−1)/q} − 1, *n*) = 1 for each prime *q*|*f*, then *n* is prime if *f* > √n.

As an example, let’s consider the primality of *n* = 2^{89}−1. A probable-prime test suggests that *n* is prime. Trial division by the primes less than a thousand tells us that *n* = 2 · 3 · 5 · 17 · 23 · 89 · 353 · 397 · 683 · 6194349127121 + 1 = 99924948842910 · 6194349127121 + 1, where the primality of 6194349127121 is indeterminate (it’s composite, but we don’t care). Since *f* = 99924948842910 is greater than the square root of *n*, we will be able to prove the primality of *n* by Pocklington’s theorem.

Consider first the situation *a* = 2; we can choose any *a* randomly from the range 1 < *a* < *n* − 1, but it is easiest to choose *a* from the sequence 2, 3, 4, …. Now 2^{n−1} ≡ 1 (mod *n*), so the first criterion holds, but 2^{(n−1)/2} ≡ 1 (mod *n*), so the gcd is *n*, and the second criterion fails. Next we consider *a* = 3. Now 3^{n−1} ≡ 1 (mod *n*), so the first criterion holds, and the second criterion holds for each *q* ∈ {2, 3, 5, 17, 23, 89, 353, 397, 683}, so *n* = 2^{89} − 1 is prime.

Brillhart, Lehmer and Selfridge later extended Pocklington’s theorem to work with *f* between the cube root and square root of *n*. The idea is to determine the constants *c*_{1} and *c*_{2} such that *n* = *c*_{2} · *f*^{2} + *c*_{1} · *f*^{1} + 1, which is easily done by extracting the “digits” of *n* to the base *f*. Then *n* is composite if *c*_{1}^{2} − 4 *c*_{2} is a perfect square and prime if it is not; Pocklington’s criteria must also hold.

With this extension to Pocklington’s theorem we can prove the primality of 2^{89} − 1 with only the factors less than 500. With *a* = 3, Pocklington’s first criterion holds, and Pocklington’s second criterion holds for each *q* ∈ {2, 3, 5, 17, 23, 89, 353, 397}, and *f* = 146302999770 is greater than the cube root of *n*, so we calculate *n* = 28917 *f*^{2} + 96609474553 *f* + 1, then 96609474553^{2} − 4 · 28917 = 9333390573406754434141 = 12611 · 95783 · 7726832165257 is not a perfect square, so *n* is prime.

Pocklington’s method fails if you can’t find sufficient factors of *n* − 1. We prefer trial division rather than some more powerful method because we have to prove that each of the factors is prime, and trial division does that for us automatically; if you can’t factor *n*−1 by trial division, but you can factor it by Pollard’s rho method or something even more powerful, you could still use Pocklington’s theorem, proving each of the factors prime by using Pocklington’s theorem on each of them recursively. For instance, if you are determined to prove the primality of *n* = 2^{521} − 1, trial division by the primes less than a thousand finds the factors 2, 3, 5, 5, 11, 17, 31, 41, 53, 131, 157 and 521, and Pollard’s rho method quickly finds the factors 1613, 2731, 8191, 42641, 51481, 61681, 409891, and 858001, all of which can be proved prime by Pocklington’s method. Taken together, the product of those factors is greater than the cube root of *n*, so you can prove the primality of 2^{521} − 1 even though you can’t factor *n* − 1 by trial division. Of course, it is still possible that you can’t find enough factors (as an example, try to prove the primality of 2^{607} − 1), in which case you need a more powerful method, but that’s a topic for a different exercise.

Your task is to write a program that proves the primality of an input number *n*, or shows that it is composite, using the method of Pocklington with extensions from Brillhart, Lehmer and Selfridge. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

I’m not sure what happens when sufficient factors are found but the number is composite. You would have to test every a where 1 < a < n – 1, which is a heck of a lot of candidates. For that matter, what if a number is prime, but the witness is closer to n-1 than 1?

If N is composite, you will waste a lot of time trying to prove that it is prime. Sorry. That’s why you should do one or several probable-prime tests before you start.

It seems to not be widely known that in the Pocklington test, the “a” doesn’t have to be the same for each (or any 2) prime q|f. There just needs to be some aq that passes for each q.

This is mentioned in Handbook of Applied Cryptography, 4.7 Notes and further references: “In Fact 4.38, the integer a does not have to be the same for all q. […] The same is true of Fact 4.40, which is due to Pocklington [981].”

So, in the algorithm described above, it’s unnecessary to stop testing with a=2 just because one of the factors failed, and for a=3 and, more importantly, it’s unnecessary to re-test any q that already passed with any earlier ‘a’.

Hello, I’m a prime numbers fan and I have some cuestions about “extended Pocklington’s theorem”:

1-What method are you using to calculate c1 and c2?, I understand you resolve this equation with Bezout id:

n = C2 f^2 + C1 f + 1

n-1 = C2 f^2 + C1 f (type y=xa+xb “diofantic equation” with y=n-1, a= f^2, b=f, x=C2, y=C1)

but the are infinite solutions the first in your example can be C2=0 and C1=4230740453823643 and you have C2=28917 and C1=96609474553. Are all solutions avalaible to test the perfect square condition?

2-If f need to be between cube root and square root of n. You have:

cube root < f < square root?

but in example "f = 146302999770 is greater than the cube root of n." you are not comparing if f = 146302999770 < square root.

3-Can you apply this extension without Pocklington original?

I understand if c1 and c2 hold the perfect square conditions you know if number is prime or not. Why it's necessary to prove pocklington first?

4-Is this the best method to calculate primality of n knowing factors of n-1? Where can I see the implementation?

Regards from Spain

@Adrian: Welcome to Programming Praxis!

1) c1 and c2 are calculated as the “digits” of n to the base f.

2) f can be larger than the square root of n. If it is, that simplifies the calculation. If not, the primality of n can be proved as long as f is greater than the cube root of n.

3) Because that’s the way the algorithm works.

4) If you know all the factors of n-1 you can use Lucas’ algorithm instead of Pocklington’s. You can see the implementation by following the links in the last paragraph or by clicking through to Page 2 of the blog entry.