Primality Checking, Revisited

January 26, 2010

[ There is a bug in the solution of this exercise. See the revised version of the exercise for a proper solution. ]

We examined the Miller-Rabin probabilistic primality checker in a previous exercise. Today, we examine a primality checker that combines the Miller-Rabin test with a test on Lucas pseudoprimes, devised by Robert Baillie and described by Baillie and Wagstaff in their article “Lucas Pseudoprimes” in Mathematics of Computation, Volume 35, Number 152, pages 1391-1417, October 1980; see also Thomas Nicely’s web page devoted to Baillie’s test. This is the same algorithm used in the PrimeQ function in Mathematica.

Lucas numbers are defined by a recurrence formula similar to Fibonacci numbers, where L_n = L_{n-1} + L_{n-2} with L_1 = 1 and L_2 = 3; the Lucas numbers are 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, … (Sloane’s A000204). Lucas numbers have the rather startling property that, if n is prime, L_n \equiv 1 \pmod{n}. But the converse is not true, and composite numbers n such that L_n \equiv 1 \pmod{n} are known as Lucas pseudoprimes; the first few Lucas pseudoprimes are 705, 2465, 2737, 3745, 4171, … (Sloane’s A005845).

Lucas numbers are a special case of Lucas sequences. If P and Q are integers such that the discriminant D = P^2 - 4Q, then the roots of x^2 - P x + Q = 0 are a = \frac{P + \sqrt{D}}{2} and b = \frac{P - \sqrt{D}}{2}. There are two Lucas sequences U_n(P, Q) = \frac{a^n - b^n}{a - b} and V_n(P, Q) = a^n + b^n for n \geq 0, which can be computed by the recurrence equations U_m(P,Q) = P U_{m-1}(P,Q) - Q U_{m-2}(P,Q) and V_m(P,Q) = P V_{m-1}(P,Q) - Q V_{m-2}(P,Q). The Lucas numbers are given by the sequence V(1,-1) and the Fibonacci numbers are given by the sequence U(1,-1).

We will want to compute the nth element of a Lucas sequence, mod n, for large n. Rather than computing the entire recurrence in time proportional to n, it is possible to use doubling and halving, in the same way as the exercise on Three Binary Algorithms, to compute the nth element in log n time. Such a computation is known as a Lucas chain.

Thus, to test whether an odd number n is a Lucas pseudoprime, we choose sequence parameters P and Q so that the the discriminant D is non-square and the Legendre number \left( \begin{array}{c} D \\ n\end{array} \right) = -1 (otherwise the modular arithmetic would fail). Then we construct the Lucas chain; if the nth element is zero modulo n, then n is either prime or is a Lucas pseudoprime.

Recall that the Miller-Rabin test used strong pseudoprime tests on fifty bases to check primality. Using Lucas pseudoprimes, we can reduce the number of tests substantially. It turns out that combining two strong pseudoprime tests, with bases 2 and 3, with a Lucas pseudoprime test, there are no known pseudoprimes; the test has been performed exhaustively on all numbers less than 1016, and no counter-examples have been found in over twenty-five years of use (in addition to fifteen minutes of fame, there is a monetary reward from the original authors for the finder of a counter-example).

Your task is to write a function that checks primality using the algorithm described above. 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.

Advertisement

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
2 Comments »