**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 and Wagstaff define Lucas pseudoprimes as follows:^{[1]} Given integers *P* and *Q*, where *P* > 0 and ,
let *U _{k}*(

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:

(1) |

If this congruence does *not* hold, then *n* is *not* prime.
If *n* is *composite*, then this congruence *usually* does not hold.^{[1]} 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),^{[2]} pages 142–152 of the book by Crandall and Pomerance,^{[3]} and pages 53–74 of the book by Ribenboim.^{[4]}

A **Lucas probable prime** for a given (*P, Q*) pair is *any* positive integer *n* for which equation (**1**) above is true (see,^{[1]} page 1398).

A **Lucas pseudoprime** for a given (*P, Q*) pair is a positive *composite* integer *n* for which equation (**1**) is true (see,^{[1]} 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,^{[1]} page 1024 of, ^{[5]} or pages 266–269 of ^{[2]}
). 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 ^{[1]} and described below).

If then equation (**1**) becomes

(2) |

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 OEIS: A006190: *U _{0}* = 0,

First, let *n* = 19. The Jacobi symbol is −1, so δ(*n*) = 20, *U _{20}* = 6616217487 = 19·348221973 and we have

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 = −1, and we can compute

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, ...

Now, factor into the form where is odd.

A **strong Lucas pseudoprime** for a given (*P, Q*) pair is an odd composite number *n* with GCD(*n, D*) = 1, satisfying one of the conditions

or

for some 0 ≤ *r* < *s*; see page 1396 of.^{[1]} A strong Lucas pseudoprime is also a Lucas pseudoprime (for the same (*P, Q*) pair), but the converse is not necessarily true.
Therefore, the **strong** test is a more stringent primality test than equation (**1**).

There are infinitely many strong Lucas pseudoprimes, and therefore, infinitely many Lucas pseudoprimes.
Theorem 7 in ^{[1]} states: Let and be relatively prime positive integers for which is positive but not a square. Then there is a positive constant (depending on and ) such that the number of strong Lucas pseudoprimes not exceeding is greater than , for sufficiently large.

We can set *Q* = −1, then and are *P*-Fibonacci sequence and *P*-Lucas sequence, the pseudoprimes can be called **strong Lucas pseudoprime in base P**, for example, the least strong Lucas pseudoprime with

An **extra strong Lucas pseudoprime**
^{[6]}
is a strong Lucas pseudoprime for a set of parameters (*P*, *Q*) where *Q* = 1, satisfying one of the conditions

or

for some . An extra strong Lucas pseudoprime is also a strong Lucas pseudoprime for the same pair.

Before embarking on a probable prime test, one usually verifies that *n*, the number to be tested for primality, is odd, is not a perfect square, and is not divisible by any small prime less than some convenient limit. Perfect squares are easy to detect using Newton's method for square roots.

We choose a Lucas sequence where the Jacobi symbol , so that δ(*n*) = *n* + 1.

Given *n*, one technique for choosing *D* is to use trial and error to find the first *D* in the sequence 5, −7, 9, −11, ... such that . Note that .
(If *D* and *n* have a prime factor in common, then ).
With this sequence of *D* values, the average number of *D* values that must be tried before we encounter one whose Jacobi symbol is −1 is about 1.79; see,^{[1]} p. 1416.
Once we have *D*, we set and .
It is a good idea to check that *n* has no prime factors in common with *P* or *Q*.
This method of choosing *D*, *P*, and *Q* was suggested by John Selfridge.

(This search will never succeed if *n* is square, and conversely if it does succeed, that is proof that *n* is not square. Thus, some time can be saved by delaying testing *n* for squareness until after the first few search steps have all failed.)

Given *D*, *P*, and *Q*, there are recurrence relations that enable us to quickly compute and in steps; see Lucas sequence § Other relations. To start off,

First, we can double the subscript from to in one step using the recurrence relations

- .

Next, we can increase the subscript by 1 using the recurrences

- .

If is odd, replace it with ; this is even so it can now be divided by 2. The numerator of is handled in the same way. (Adding *n* does not change the result modulo *n*.)
Observe that, for each term that we compute in the *U* sequence, we compute the corresponding term in the *V* sequence. As we proceed, we also compute the same, corresponding powers of *Q*.

At each stage, we reduce , , and the power of , mod *n*.

We use the bits of the binary expansion of *n* to determine *which* terms in the *U* sequence to compute. For example, if *n*+1 = 44 (= 101100 in binary), then, taking the bits one at a time from left to right, we obtain the sequence of indices to compute: 1_{2} = 1, 10_{2} = 2, 100_{2} = 4, 101_{2} = 5, 1010_{2} = 10, 1011_{2} = 11, 10110_{2} = 22, 101100_{2} = 44. Therefore, we compute *U*_{1}, *U*_{2}, *U*_{4}, *U*_{5}, *U*_{10}, *U*_{11}, *U*_{22}, and *U*_{44}. We also compute the same-numbered terms in the *V* sequence, along with *Q*^{1}, *Q*^{2}, *Q*^{4}, *Q*^{5}, *Q*^{10}, *Q*^{11}, *Q*^{22}, and *Q*^{44}.

By the end of the calculation, we will have computed *U _{n+1}*,

When *D*, *P*, and *Q* are chosen as described above, the first 10 Lucas pseudoprimes are (see page 1401 of ^{[1]}):
323, 377, 1159, 1829, 3827, 5459, 5777, 9071, 9179, and 10877 (sequence A217120 in the OEIS)

The **strong** versions of the Lucas test can be implemented in a similar way.

When *D*, *P*, and *Q* are chosen as described above, the first 10 *strong* Lucas pseudoprimes are: 5459, 5777, 10877, 16109, 18971, 22499, 24569, 25199, 40309, and 58519
(sequence A217255 in the OEIS)

To calculate a list of *extra strong* Lucas pseudoprimes, set .
Then try *P* = 3, 4, 5, 6, ..., until a value of is found so that the Jacobi symbol .
With this method for selecting *D*, *P*, and *Q*, the first 10 *extra strong* Lucas pseudoprimes are
989, 3239, 5777, 10877, 27971, 29681, 30739, 31631, 39059, and 72389
(sequence A217719 in the OEIS)

If we have checked that congruence (**2**) is true, there are additional congruence conditions we can check that have almost no additional computational cost.
If *n* happens to be composite, these additional conditions may help discover that fact.

If *n* is an odd prime and , then we have the following (see equation 2 on page 1392 of ^{[1]}):

(3) |

Although this congruence condition is not, by definition, part of the Lucas probable prime test, it is almost free to check this condition because, as noted above, the value of *V _{n+1}* was computed in the process of computing

If either congruence (**2**) or (**3**) is false, this constitutes a proof that *n* is not prime.
If *both* of these congruences are true, then it is even more likely that *n* is prime than if we had checked only congruence (**2**).

If Selfridge's method (above) for choosing *D*, *P*, and *Q* happened to set *Q* = −1, then we can adjust *P* and *Q* so that *D* and remain unchanged and *P* = *Q* = 5 (see Lucas sequence-Algebraic relations).
If we use this enhanced method for choosing *P* and *Q*, then 913 = 11·83 is the *only* composite less than 10^{8} for which congruence (**3**) is true (see page 1409 and Table 6 of;^{[1]}). More extensive calculations show that, with this method of choosing *D*, *P*, and *Q*, there are only five odd, composite numbers less than 10^{15} for which congruence (**3**) is true.^{[7]}

If , then a further congruence condition that involves very little additional computation can be implemented.

Recall that is computed during the calculation of , and we can easily save the previously computed power of , namely, .

If *n* is prime, then, by Euler's criterion,

- .

(Here, is the Legendre symbol; if *n* is prime, this is the same as the Jacobi symbol).

Therefore, if *n* is prime, we must have,

(4) |

The Jacobi symbol on the right side is easy to compute, so this congruence is easy to check.
If this congruence does not hold, then *n* cannot be prime. Provided GCD(*n, Q*) = 1 then testing for congruence (**4**) is equivalent to augmenting our Lucas test with a "base Q" Solovay–Strassen primality test.

Additional congruence conditions that must be satisfied if *n* is prime are described in Section 6 of.^{[1]} If *any* of these conditions fails to hold, then we have proved that *n* is not prime.

*k* applications of the Miller–Rabin primality test declare a composite *n* to be probably prime with a probability at most (1/4)^{k}.

There is a similar probability estimate for the strong Lucas probable prime test.^{[8]}

Aside from two trivial exceptions (see below), the fraction of (*P*,*Q*) pairs (modulo *n*) that declare a composite *n* to be probably prime is at most (4/15).

Therefore, *k* applications of the strong Lucas test would declare a composite *n* to be probably prime with a probability at most (4/15)^{k}.

There are two trivial exceptions. One is *n* = 9. The other is when *n* = *p*(*p*+2) is the product of two twin primes. Such an *n* is easy to factor, because in this case, *n*+1 = (*p*+1)^{2} is a perfect square. One can quickly detect perfect squares using Newton's method for square roots.

By combining a Lucas pseudoprime test with a Fermat primality test, say, to base 2, one can obtain very powerful probabilistic tests for primality, such as the Baillie–PSW primality test.

When *P* = 1 and *Q* = −1, the *U _{n}*(

A **Fibonacci pseudoprime** is often^{[2]}^{: 264, }^{[3]}^{: 142, }^{[4]}^{: 127 }
defined as a composite number *n* not divisible by 5 for which congruence (**1**) holds with *P* = 1 and *Q* = −1. By this definition, the Fibonacci pseudoprimes form a sequence:

- 323, 377, 1891, 3827, 4181, 5777, 6601, 6721, 8149, 10877, ... (sequence A081264 in the OEIS).

The references of Anderson and Jacobsen below use this definition.

If *n* is congruent to 2 or 3 modulo 5, then Bressoud,^{[2]}^{: 272–273 } and Crandall and Pomerance^{[3]}^{: 143, 168 } point out that it is rare for a Fibonacci pseudoprime to also be a Fermat pseudoprime base 2. However, when *n* is congruent to 1 or 4 modulo 5, the opposite is true, with over 12% of Fibonacci pseudoprimes under 10^{11} also being base-2 Fermat pseudoprimes.

If *n* is prime and GCD(*n*, *Q*) = 1, then we also have^{[1]}^{: 1392 }

(5) |

This leads to an alternative definition of Fibonacci pseudoprime:^{[9]}^{[10]}

- a
**Fibonacci pseudoprime**is a composite number*n*for which congruence (**5**) holds with*P*= 1 and*Q*= −1.

This definition leads the Fibonacci pseudoprimes form a sequence:

- 705, 2465, 2737, 3745, 4181, 5777, 6721, 10877, 13201, 15251, ... (sequence A005845 in the OEIS),

which are also referred to as *Bruckman-Lucas* pseudoprimes.^{[4]}^{: 129 }
Hoggatt and Bicknell studied properties of these pseudoprimes in 1974.^{[11]} Singmaster computed these pseudoprimes up to 100000.^{[12]} Jacobsen lists all 111443 of these pseudoprimes less than 10^{13}.^{[13]}

It has been shown that there are no even Fibonacci pseudoprimes as defined by equation (5).^{[14]}^{[15]} However, even Fibonacci pseudoprimes do exist (sequence A141137 in the OEIS) under the first definition given by (**1**).

A **strong Fibonacci pseudoprime** is a composite number *n* for which congruence (**5**) holds for *Q* = −1 and all *P*.^{[16]} It follows^{[16]}^{: 460 } that an odd composite integer *n* is a strong Fibonacci pseudoprime if and only if:

*n*is a Carmichael number- 2(
*p*+ 1) | (*n*− 1) or 2(*p*+ 1) | (*n*−*p*) for every prime*p*dividing*n*.

The smallest example of a strong Fibonacci pseudoprime is 443372888629441 = 17·31·41·43·89·97·167·331.

A **Pell pseudoprime** may be defined as a composite number *n* for which equation (**1**) above is true with *P* = 2 and *Q* = −1; the sequence *U _{n}* then being the Pell sequence. The first pseudoprimes are then 35, 169, 385, 779, 899, 961, 1121, 1189, 2419, ...

This differs from the definition in OEIS: A099011 which may be written as:

with (*P*, *Q*) = (2, −1) again defining *U _{n}* as the Pell sequence. The first pseudoprimes are then 169, 385, 741, 961, 1121, 2001, 3827, 4879, 5719, 6215 ...

A third definition uses equation (5) with (*P*, *Q*) = (2, −1), leading to the pseudoprimes 169, 385, 961, 1105, 1121, 3827, 4901, 6265, 6441, 6601, 7107, 7801, 8119, ...