# More details about the Baillie–PSW test

It's clear that Mathematica uses the Baillie–PSW test for its PrimeQ function (which tests primality), and as I read in the Mathematica documentation, it starts with trial division, then base 2 and 3 Miller–Rabin, and then Lucas pseudoprime test. My question is:

Can we remove base 2 and 3 and use only a random base?

The advantage in using base 2 is that we know all of the psp's base 2 up to $2^{64}$. It has been verified that none of these psp(2)'s passes a Lucas test when the parameters $P, Q$ are chosen in accord with any of the methods in the Baillie/Wagstaff paper.

If you choose a random base, there might be some composite $n$ that passes both the Fermat and Lucas tests. For example, $n = 5777$ is a strong psp base 76, and is also a Lucas pseudoprime.

By the way, if you implement a Lucas test, I would also recommend adding the following check, which is virtually free once you reach the end of the Lucas calculation. If $n$ is an odd prime and $(n, QD) = 1$ where $D = P^2 - 4Q$, (and, as usual, $\left(\frac{D}{n}\right) = -1$ (a Jacobi symbol), then $V_{n+1} \equiv 2Q \pmod n$. If $D, P$, and $Q$ are chosen by method $A^*$ (see Baillie/Wagstaff), then 913 is the only odd composite number up to 25 billion for which this congruence holds. (The B/W paper gives a limit of $10^8$, but I've recently carried the calculation farther). So, in addition to the sprp(2) and slprp(P,Q) tests, this congruence adds additional strength to the primality test.

References for the test:

• Pomerance, Selfridge, Wagstaff, "The Pseudoprimes to 25 x 10^9", July 1980. Page 1024-1025, Check if n is a strong probable prime base 2. Check whether n is a Lucas probable prime using method A (Selfridge) or B. The authors offer \$30 to the first finder of a counterexample or proof of non-existence. It references the next paper when discussing the test.

• Baillie and Wagstaff, "Lucas Pseudoprimes", October 1980. Page 1401. Trial divide to some convenient limit. Check whether n is a strong probable prime base 2. Check whether n is a strong Lucas probable prime using method A (Selfridge) or B.

• Pomerance, "Are there counter-examples to the Baillie-PSW Primality Test?", 1984. References PSW80: Check whether n is a strong probable prime base 2. Check whether n is a Lucas probable prime using the Selfridge parameters (method A). He mentions that even if condition 1 is weakened, every composite to n <= 25*10^9 still fails. The short paper repeatedly calls this combination of a strong base-2 prp and Lucas-Selfridge prp tests the "Baillie-PSW" test.

All of these describe using a strong base-2 probable prime test. The slightly earlier PSW paper indicates a Lucas test, while the BW paper recommends a strong Lucas test. The 1980 papers indicate that one of two specific parameter selection methods should be used, while Pomerance's 1984 paper drops the non-Selfridge method.

In my opinion, the paper by Baillie and Wagstaff is the primary reference, though should be read in combination with Pomerance, Selfridge, and Wagstaff. Consensus over time is that the Selfridge (method A) parameter selection should be used. Other variations commonly used include the extra-strong test, the "almost" extra-strong test, and Frobenius tests. See the page "Pseudoprime statistics, Data, and Tables" for more info and links.