Programming Praxis

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ⁿ⁻¹ ≡ 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⁸⁹−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ⁿ⁻¹ ≡ 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ⁿ⁻¹ ≡ 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⁸⁹ − 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₁ and c₂ such that n = c₂ · f² + c₁ · f¹ + 1, which is easily done by extracting the “digits” of n to the base f. Then n is composite if c₁² − 4 c₂ 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⁸⁹ − 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² + 96609474553 f + 1, then 96609474553² − 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⁵²¹ − 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⁵²¹ − 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⁶⁰⁷ − 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.

Pages: 1 2