FLINT3.7.0-dev
/

n_is_probabprime_BPSW

Synopsis#include <flint/ulong_extras.h>
int n_is_probabprime_BPSW(ulong n)source

Baillie–PSW probable prime test [PSW1980; BaiWag1980]. No composite passing it is known, and it has been checked against tables of pseudoprimes up to 2^{64}, so it is a primality test for word-size n.

This variant of BPSW, following [Chen2003], uses a Fibonacci test instead of a Lucas test when n \equiv 2, 3 \pmod 5 (see also [CraPom2005], p. 143).

References#

  • [PSW1980] C. Pomerance, J. L. Selfridge and S. S. Wagstaff, Jr., "The pseudoprimes to 25·10^9", Mathematics of Computation 35 (1980), 1003–1026
  • [BaiWag1980] Robert Baillie; Samuel S. Wagstaff, Jr. (October 1980). "Lucas Pseudoprimes". Mathematics of Computation. 35 (152): 1391–1417.
  • [Chen2003] Zhuo Chen and John Greene : Some Comments on Baillie–PSW Pseudoprimes, The Fibonacci Quarterly 41:4 (2003) 334–344
  • [CraPom2005] R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspective, second edition, Springer (2005).
Cite this page

The FLINT team, “n_is_probabprime_BPSW (ulong_extras.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/ulong_extras/n_is_probabprime_BPSW.html (generated 2026-10-20).