It is named after Robert Baillie, Carl Pomerance, John Selfridge, and Samuel Wagstaff.
For example, Fermat pseudoprimes to base 2 tend to fall into the residue class 1 (mod m) for many small m, whereas Lucas pseudoprimes tend to fall into the residue class −1 (mod m).
If you choose a random base, there might be some composite n that passes both the Fermat and Lucas tests.
No composite number below 264 (approximately 1.845·1019) passes the strong or standard Baillie–PSW test,[3] that result was also separately verified by Charles Greathouse in June 2011.
In 1980, the authors Pomerance, Selfridge, and Wagstaff offered $30 for the discovery of a counterexample, that is, a composite number that passed this test.
Arnault [11] gives a 397-digit Carmichael number N that is a strong pseudoprime to all prime bases less than 307.
Because this N is a Carmichael number, N is also a (not necessarily strong) pseudoprime to all bases less than p, where p is the 131-digit smallest prime factor of N. A quick calculation shows that N is not a Lucas probable prime when D, P, and Q are chosen by the method described above, so this number would be correctly determined by the Baillie–PSW test to be composite.
The following computer algebra systems and software packages use some version of the Baillie–PSW primality test.
[17] The BigInteger class in standard versions of Java and in open-source implementations like OpenJDK has a method called isProbablePrime.
In Python, the NZMATH[23] library has the strong pseudoprime and Lucas tests, but does not have a combined function.
[27]: Table 1 For some of the latter, Albrecht, et al. were able to construct composite numbers that the libraries declared to be prime.