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 D = P 2 − 4 Q {\displaystyle D=P^{2}-4Q} , let Uk(P, Q) and Vk(P, Q) be the corresponding Lucas sequences. Let n be a positive integer and let ( D n ) {\displaystyle \left({\tfrac {D}{n}}\right)} be the Jacobi symbol. We define
δ ( n ) = n − ( D n ) . {\displaystyle \delta (n)=n-\left({\tfrac {D}{n}}\right).}
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 (1) 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 (1) above is true (see, page 1398). A Lucas pseudoprime for a given (P, Q) pair is a positive composite integer n for which equation (1) is true (see, page 1391). A Lucas probable prime test is most useful if D is chosen such that the Jacobi symbol ( D n ) {\displaystyle \left({\tfrac {D}{n}}\right)} 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 ( D n ) = − 1 , {\displaystyle \left({\tfrac {D}{n}}\right)=-1,} then equation (1) becomes
If congruence (2) is false, this constitutes a proof that n is composite. If congruence (2) is true, then n is a Lucas probable prime. In this case, either n is prime or it is a Lucas pseudoprime. If congruence (2) 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 with different D, P and Q, then unless one of the tests proves that n is composite, we gain more confidence that n is prime. Examples: If P = 3, Q = −1, and D = 13, the sequence of U's is (sequence A006190 in the OEIS): U0 = 0, U1 = 1, U2 = 3, U3 = 10, etc. First, let n = 19. The Jacobi symbol ( 13 19 ) {\displaystyle \left({\tfrac {13}{19}}\right)} is −1, so δ(n) = 20, U20 = 6616217487 = 19·348221973 and we have
U 20 = 6616217487 ≡ 0 ( mod 19 ) . {\displaystyle U_{20}=6616217487\equiv 0{\pmod {19}}.}
Therefore, 19 is a Lucas probable prime for this (P, Q) pair. In this case 19 is prime, so it is not a Lucas pseudoprime. For the next example, let n = 119. We have ( 13 119 ) {\displaystyle \left({\tfrac {13}{119}}\right)} = −1, and we can compute
U 120 ≡ 0 ( mod 119 ) . {\displaystyle U_{120}\equiv 0{\pmod {119}}.}
However, 119 = 7·17 is not prime, so 119 is a Lucas pseudoprime for this (P, Q) pair. In fact, 119 is the smallest pseudoprime for P = 3, Q = −1. We will see below that, in order to check equation (2) for a given n, we do not need to compute all of the first n + 1 terms in the U sequence. Let Q = −1, the smallest Lucas pseudoprime to P = 1, 2, 3, ... are
323, 35, 119, 9, 9, 143, 25, 33, 9, 15, 123, 35, 9, 9, 15, 129, 51, 9, 33, 15, 21, 9, 9, 49, 15, 39, 9, 35, 49, 15, 9, 9, 33, 51, 15, 9, 35, 85, 39, 9, 9, 21, 25, 51, 9, 143, 33, 119, 9, 9, 51, 33, 95, 9, 15, 301, 25, 9, 9, 15, 49, 155, 9, 399, 15, 33, 9, 9, 49, 15, 119, 9, ...
… excerpt ends here. Continue reading the full article.
