The Baillie-PSW Primality Test (2024)

Last updated 0700 GMT 13 January 2012. Originally posted 10 June 2005.

• Bibliography

The Baillie-PSW (BPSW or BSW) primality test is actually a compositenesstest, in the manner of Fermat's test and the Miller-Rabin test. It is namedfor Robert Baillie, Carl Pomerance, John L. Selfridge, and Samuel S.Wagstaff, Jr. The algorithm was apparently first conceived by Baillie(Baillie and Wagstaff, 1980), with refinements added by Selfridge (Pomerance,Selfridge, and Wagstaff, 1980). The procedure is as follows; note that somedetails may vary from one implementation to another (Martin, 2004).

• Process all N < 3 and all even N.
• Check N for any small prime divisors p < 1000.
• Perform a Miller-Rabin (strong probable prime) test, base 2, on N.
• Perform a (standard or strong) Lucas-Selfridge test on N, using Lucas sequences with the parameters suggested by Selfridge.

As of this date, both the standard and strong tests are flawless; nocounterexample (BPSW standard or strong pseudoprime) is known.With the aid of Richard G. E. Pinch's table of base-2 strong pseudoprimes,the author verified (May, 2005) that no BPSW pseudoprime (standardor strong) exists for N < 10^13. In January, 2007, with the aid ofthe author's code andWilliam Galway's tableof pseudoprimes, Martin Fuller determined that no BPSWpseudoprime (standard or strong) exists for N < 10^15. More recently,JeffGilchrist, using the author's code anda database ofpseudoprimes prepared by Jan Feitsma, has verified (13 June 2009)that no BPSW pseudoprime (standard or strong) exists below 10^17.Furthermore, analysis (24 October 2009) by Gilchrist of an extension ofFeitsma's database to 2^64 found no BPSW pseudoprime (standard orstrong) below 2^64 (approximately 1.8446744e19). This lower bound of 2^64for any BPSW pseudoprime has since been separately verified (11 July 2011)by Charles Greathouse; however, he also used Feitsma's database, so acompletely independent check has not yet been carried out.

Note, however, that Carl Pomerance (1984) presented a heuristic argumentthat an infinite number of counterexamples exist to the standard test(and presumably to the strong test as well, based on similar reasoning),and even that (for sufficiently large x, dependent on µ) the numberof BPSW pseudoprimes < x exceeds x^(1-µ), where µ isan arbitrarily small pre-assigned positive number. Nevertheless, not asingle BPSW pseudoprime has yet been found. Consequently, theBPSW test carries an aura of dependability (justified or not)exceeding that of competing algorithms, such as multiple Miller-Rabintests.

It is believed that some commercial mathematics software packagesrely, in part or in whole, on the BPSW test for primalitychecking; see, for example, Ribenboim (1995/6, p. 142), alsoMartin (2004). In some instances, these packages appear to use thestrong BPSW and/or Lucas test, or add additional Miller-Rabin tests.

BPSW requires O((log n)^3) bit operations, as do Fermat'stest and the Miller-Rabin algorithm. However, a BPSW testtypically requires roughly three to seven times as many bitoperations as a single Miller-Rabin test. The strong version ofBPSW differs only in replacing the standard Lucas-Selfridge testwith the strong Lucas-Selfridge test. The strong Lucas-Selfridgetest produces only roughly 30 % as many pseudoprimes as thestandard version; for example, among the odd composites N < 10^6,there are 219 standard Lucas-Selfridge pseudoprimes, 58 strongLucas-Selfridge pseudoprimes, and 46 base-2 strong pseudoprimes(these totals presume no screening with odd trial divisors).Since the strong Lucas-Selfridge test incurs roughly 10 % morerunning time, the strong tests appear to be more effective.

Selfridge specified the following parameters for the generationof the Lucas sequences: P = 1 and Q = (1 - D)/4, where D is thefirst integer in the sequence {5, -7, 9, -11, 13, -15, ...} forwhich GCD(D,N)=1 and the Jacobi symbol (D|N) = -1. Note, however,that if N is a perfect square, no such D will exist, and thesearch for D would continue all the way to ±sqrt(N), at whichpoint GCD(D,N)=sqrt(N) would expose N as composite. Consequently,the algorithm also presumes the presence of a preliminary checkfor perfect squares (as well as even integers and integers < 3).

Additional conditions sometimes imposed (Riesel, 1994, p. 130),that N not divide Q and that D be square-free, were found to beirrelevant to this application of Lucas sequences.

There remains the theoretical concern that, for very large N,the required D would be so large in magnitude that the algorithmwould become computationally useless. Given the exclusion ofperfect square values of N, no such behavior has been observedin practice; indeed, the range of values observed for D is quitesmall---|D|max=47 for N < 10^6, |D|max=67 for10^19 < N < 10^19 + 10^6. Baillie and Wagstaff (1980) presentedanalytical arguments to support this observation (Ribenboim, 1995/6,p. 142). However, the eventuality cannot be entirely excluded, andthe author's code includes an overflow trap for D.

The author has translated the algorithm into GNU C, employing the GMPlibrary, with a command-line executable compiled for the DOS/Winteloperating environment; see the accompanyingzipfile, which includes the source codes andWintel/DOS executables. To examine the complete library source modulesor to recompile the codes, you will also need to download the supportfiles trn.c and trn.h from trn.zip. Theillustrative main routine computes pi(x) between specified bounds, andenumerates the corresponding pseudoprimes produced by various primalitytests, including the standard and strong BPSW tests (none foundto date), the standard, strong, and extra strong Lucas tests, and variousothers, including the Fermat and Miller-Rabin tests (base 2) as well asthe GMP mpz_probab_prime_p function (seeGNU GMP mpz_probab_prime_p pseudoprimes).

Code is also included in trn.c for the "extra strong" Lucastest, as developed by Zhaiyu Mo and James P. Jones (circa 1997),and described by Jon Grantham (1998). However, I have not employed theextra strong Lucas test in the BPSW test, as the Lucas sequenceparameters are inconsistent with those of the Lucas-Selfridge tests;consequently, the extra strong Lucas pseudoprimes were not found to bedisjoint from those of the Miller-Rabin test with base 2 (or any othersingle Miller-Rabin base employed). This behavior was observed for allbases employed for the extra strong Lucas test. For a more detaileddiscussion, see the documentation in the module iExtraStrongLucas inthe support file trn.c included in trn.zip.

I would appreciate notification of any significant errors found in thisdocument, the codes, or their results.

BIBLIOGRAPHY

• Arnault, François. The Rabin-Monier theorem for Lucas pseudoprimes. Math. Comp. 66 (1997) 869-881.
• Baillie, Robert, and Samuel S. Wagstaff, Jr. Lucas pseudoprimes. Math. Comp. 35 (1980) 1391-1417.
• Feitsma, Jan. The pseudoprimes below 10^17. June 2009.
• Fuller, Martin. Personal e-mail communications, 19-21 January 2007.
• Galway, William. The pseudoprimes below 10^15. 4 November 2002.
• Gilchrist, Jeff. Pseudoprime enumeration with probabilistic primality tests. 13 June 2009.
• Grantham, Jon. Frobenius pseudoprimes. Preprint (16 July 1998).
• Martin, Marcel. Re: Baillie-PSW - which variant is correct? 9 January 2004.
• Miller, Gary L. Riemann's Hypothesis and tests for primality. J. Comp. Syst. Sci. 13 (1976) 300-317.
• Mo, Zhaiyu, and James P. Jones. A new primality test using Lucas sequences. Preprint (circa 1997).
• Pinch, Richard G. E. Pseudoprimes up to 10^13. Springer Lecture Notes in Computer Science 1838 (2000) 459-474.
• Pomerance, Carl. Are there counterexamples to the Baillie-PSW primality test? 1984.
• Pomerance, Carl, John L. Selfridge, and Samuel S. Wagstaff, Jr. The pseudoprimes to 25*10^9,. Math. Comp. 35 (1980) 1003-1026.
• Rabin, Michael O. Probabilistic algorithms. Symposium on new directions and recent results in algorithms and complexity. Ed. J. F. Traub. New York: Academic Press, 1976. 21-39.
• Ribenboim, Paulo. The new book of prime number records. 3rd ed. New York: Springer-Verlag, 1995/6. 53-83, 126-132, 141-142. Note that, on line 2, p. 142, in reference to the strong Lucas test, the condition "0 < r < s" should read "0 <= r < s".
• Riesel, Hans. Prime numbers and computer methods for factorization. 2nd ed. Boston: Birkhaüser, 1994. 107-130.
• Weisstein, Eric W. Baillie-PSW primality test. May, 2005.
• Weisstein, Eric W. Strong Lucas pseudoprime. May, 2005.
• Weisstein, Eric W. Extra strong Lucas pseudoprime. May, 2005. NOTE: The specified Lucas sequences should read U_n(b, 1) and V_n(b, 1); the discriminant should be b² - 4.

• Source code and executable for BPSW
• Support library modules trn.c and trn.h
• GNU GMP mpz_probab_prime_p pseudoprimes
• Home page