Programming Praxis

Since we now have a function to compute Lucas sequences, we can take another look at testing primality using Lucas pseudoprimes.

The standard version of the Lucas pseudoprime test chooses a suitableP and Q, computes the Lucas sequence U_n+1(P,Q), and declares n either prime or a Lucas pseudoprime if U_n+1(P,Q) ≡ 0 (mod n). The strong version of the Lucas pseudoprime test calculates n = d · 2^s + 1 with d odd, and declares n either prime or a Lucas pseudoprime if U_d(P,Q) ≡ 0 (mod n) or if V_{d 2^r} (P,Q) ≡ 0 (mod n) for any r with 0 ≤ r < s. John Selfridge suggested a suitable method for choosing P and Q: choose D as the smallest number in the sequence 5, -7, 9, -11, 13, -15, 17, … for which the Jacobi symbol (D / n) = -1, then set P = 1 and Q = (1 – D) / 4.

Robert Baillie and Sam Wagstaff developed a pseudoprimality test based on Lucas pseudoprimes. Their procedure has four steps: 1) If n is divisible by any prime less than 1000, then n is composite; 2) if n is not a strong probable prime to base 2, then n is composite; 3) choose parameters P and Q and declare n to be composite if it is a square; 4) If n is not a Lucas probable prime with parameters P and Q, using either the standard or strong version of the Lucas test, then n is composite. Otherwise, n is almost certainly prime. The procedure can fail only by asserting that a composite number is prime; it will never report that a prime number is composite.

Your task is to write functions to determine if n is a probable prime using the standard and strong Lucas pseudoprime test. 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