Lucas pseudoprimes and Fibonacci pseudoprimes are composite integers that pass certain tests which all primes and very few composite numbers pass: in this case, criteria relative to some Lucas sequence. Baillie-Wagstaff-Lucas pseudoprimes Baillie and Wagstaff define Lucas pseudoprimes as follows: Given integers P and Q, where P > 0 and , let Uk(P, Q) and Vk(P, Q) be the corresponding Lucas sequences. Let n be a positive integer and let be the Jacobi symbol. We define If n is a prime that does not divide Q, then the following congruence condition holds: If this congruence does not hold, then n is not prime. If n is composite, then this congruence usually does not hold. These are the key facts that make Lucas sequences useful in primality testing. The congruence () represents one of two congruences defining a Frobenius pseudoprime. Hence, every Frobenius pseudoprime is also a Baillie-Wagstaff-Lucas pseudoprime, but the converse does not always hold. Some good references are chapter 8 of the book by Bressoud and Wagon (with Mathematica code), pages 142–152 of the book by Crandall and Pomerance, and pages 53–74 of the book by Ribenboim. Lucas probable primes and pseudoprimes A Lucas probable prime for a given (P, Q) pair is any positive integer n for which equation () above is true (see, page 1398). A Lucas pseudoprime for a given (P, Q) pair is a positive composite integer n for which equation () is true (see, page 1391). A Lucas probable prime test is most useful if D is chosen such that the Jacobi symbol is −1 (see pages 1401–1409 of, page 1024 of, or pages 266–269 of ). This is especially important when combining a Lucas test with a strong pseudoprime test, such as the Baillie–PSW primality test. Typically implementations will use a parameter selection method that ensures this condition (e.g. the Selfridge method recommended in and described below). If then equation () becomes If congruence () is false, this constitutes a proof that n is composite. If congruence () is true, then n is a Lucas probable prime. In this case, either n is prime or it is a Lucas pseudoprime. If congruence () is true, then n is likely to be prime (this justifies the term probable prime), but this does not prove that n is prime. As is the case with any other probabilistic primality test, if we perform additional Lucas tests