Lucas Pseudoprimes
February 4, 2014
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 Un+1(P,Q), and declares n either prime or a Lucas pseudoprime if Un+1(P,Q) ≡ 0 (mod n). The strong version of the Lucas pseudoprime test calculates n = d · 2s + 1 with d odd, and declares n either prime or a Lucas pseudoprime if Ud(P,Q) ≡ 0 (mod n) or if Vd 2r (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.
Programming Praxis 
I believe your test description came from Nicely’s site rather than the source material. Baillie and Wagstaff, “Lucas Pseudoprimes”, October 1980. Page 1401. Pomerance, Selfridge, Wagstaff, “The Pseudoprimes to 25 x 10^9”, July 1980. Page 1024-1025. Pomerance, “Are there counter-examples to the Baillie-PSW Primality Test?”, 1984.
Baillie and Wagstaff page 1401: 1. Trial divide to some convenient limit (1000 is given as an example, but this is is just a practical step, not a requirement of the test). 2. if n is not a strong probable prime to base 2, then n is composite. 3. Choose P & Q by method A or B (A is the Selfridge method). 4. If n is not a strong Lucas probable prime with parameters P and Q, then n is a composite.
Step 1 is left out in PSW80 and P84 — it’s an obvious practical step, but not necessary. Step 2 is is “strong probable prime to base 2” in all papers. Some later authors weaken this (e.g. Chen and Greene 2003) but there is no reason to prefer the standard test to the strong test. Step 3 is selection of parameters, which P84 limits to just the Selfridge method, but the other two allow both methods (though I’ve not seen anyone use method B). Step 4 is the strong Lucas test in BW80. It is just the standard version in PSW80 (which doesn’t mention strong Lucas pseudoprimes at all) and P84.
Lots of software take different steps and still call it a BPSW test. Step 1 is just a pretest so given software can do whatever it thinks makes things faster. If one is creating a primality test now, you would want to use at leas the strong Lucas test — it runs as fast or faster than the standard test and the pseudoprimes are a subset. Pari, for example, uses a variant of the extra strong test. I prefer the full extra strong test using the Baillie parameters (A217719) since it has fewer pseudoprimes, runs faster than the standard or strong test, and maintains the same residue class behavior.
(caveat: link to my page) A comparison of some of the tests and the number of pseudoprimes can be seen here: http://www.sti15.com/nt/pseudoprimes.html
An incomplete list of various software that that performs the BPSW test and the specific tests they use can be found on the Wikipedia BPSW talk page.
[…] have heard that the extra strong test is faster than the strong test. Is this true? I find it unlikely since […]