Baillie and Wagstaff and Pomerance et al. (1980, Pomerance 1984) proposed a test (or rather a related set of tests) based on a combination of strong pseudoprimes and Lucas pseudoprimes. There are a number of variants, one particular version of which is given by the following algorithm: 1. Perform a base-2 strong pseudoprime test on n. If this test fails, declare n composite and halt. If this test success, n is probably prime. Proceed to step 2. 2. In the sequence 5, -7, 9, -11, 13, ..., find the first number D for which the Jacobi symbol (D/n) = - 1. Then perform a Lucas pseudoprime test with discriminant D on n. If this test fails, declare n composite. It if succeeds, n is very probably prime.

Lucas pseudoprime | strong pseudoprime