Baillie-PSW primality test

The Baillie-PSW primality test is a probabilistic or possibly deterministic algorithm that decides whether a number is composite or a probable prime. It is named after Robert Baillie, Carl Pomerance, John Selfridge and Samuel Wagstaff, and it combines a strong Fermat probable prime test to base 2 with a standard or strong Lucas probable prime test. Each component has its own list of pseudoprimes, composite numbers that pass it, and no overlap between the two lists is known, so a number that passes both is very likely prime. No composite number below 2 to the power 64, about 1.845 times ten to the nineteenth, passes the test, which makes it deterministic below that bound, and no composite passing it is known above that bound either. In 1980 the three authors Pomerance, Selfridge and Wagstaff offered thirty dollars for a counterexample or a proof of correctness, and a heuristic argument by Pomerance suggests that infinitely many counterexamples exist.