Lucas pseudoprimes andFibonacci pseudoprimes arecomposite integers that pass certain tests which allprimes and very few composite numbers pass: in this case, criteria relative to someLucas sequence.

Baillie and Wagstaff define Lucas pseudoprimes as follows:^[1] Given integersP andQ, whereP > 0 and${\displaystyle D=P^2-4Q}$,letU_k(P,Q) andV_k(P,Q) be the correspondingLucas sequences.

Letn be a positive integer and let${\displaystyle \left(\frac{D}{n}\right)}$ be theJacobi symbol. We define

${\displaystyle \delta (n)=n-\left(\frac{D}{n}\right).}$

Ifn is aprime that does not divideQ, then the following congruence condition holds:

${\displaystyle U_{\delta (n)}\equiv 0(\mathrm{mod}n).}$

1

If this congruence doesnot hold, thenn isnot prime.Ifn iscomposite, then this congruenceusually does not hold.^[1] These are the key facts that make Lucas sequences useful inprimality testing.

The congruence (1) represents one of two congruences defining aFrobenius 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 (withMathematica code),^[2] pages 142–152 of the book by Crandall and Pomerance,^[3] and pages 53–74 of the book by Ribenboim.^[4]

ALucas probable prime for a given (P, Q) pair isany positive integern for which equation (1) above is true (see,^[1] page 1398).

ALucas pseudoprime for a given (P, Q) pair is a positivecomposite integern for which equation (1) is true (see,^[1] page 1391).

A Lucas probable prime test is most useful ifD is chosen such that the Jacobi symbol${\displaystyle \left(\frac{D}{n}\right)}$ 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 astrong pseudoprime test, such as theBaillie–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${\displaystyle \left(\frac{D}{n}\right)=-1,}$ then equation (1) becomes

${\displaystyle U_{n+1}\equiv 0(\mathrm{mod}n).}$

2

If congruence (2) is false, this constitutes a proof thatn is composite.

If congruence (2) is true, thenn is a Lucas probable prime.In this case, eithern is prime or it is a Lucas pseudoprime.If congruence (2) is true, thenn islikely to be prime (this justifies the termprobable prime), but this does notprove thatn is prime.As is the case with any other probabilistic primality test, if we perform additional Lucas tests with differentD,P andQ, then unless one of the tests proves thatn is composite, we gain more confidence thatn is prime.

Examples: IfP = 3,Q = −1, andD = 13, the sequence ofU's is (sequenceA006190 in theOEIS):U₀ = 0,U₁ = 1,U₂ = 3,U₃ = 10, etc.

First, letn = 19. The Jacobi symbol${\displaystyle \left(\frac{13}{19}\right)}$ is −1, so δ(n) = 20,U₂₀ = 6616217487 = 19·348221973 and we have

${\displaystyle U_{20}=6616217487\equiv 0(\mathrm{mod}19).}$

Therefore, 19 is a Lucas probable prime for this (P, Q) pair. In this case 19 is prime, so it isnot a Lucas pseudoprime.

For the next example, letn = 119. We have${\displaystyle \left(\frac{13}{119}\right)}$ = −1, and we can compute

${\displaystyle U_{120}\equiv 0(\mathrm{mod}119).}$

However, 119 = 7·17 is not prime, so 119 is a Lucaspseudoprime for this (P, Q) pair.In fact, 119 is the smallest pseudoprime forP = 3,Q = −1.

We will seebelow that, in order to check equation (2) for a givenn, we donot need to compute all of the firstn + 1 terms in theU sequence.

LetQ = −1, the smallest Lucas pseudoprime toP = 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${\displaystyle \delta (n)=n-\left(\frac{D}{n}\right)}$ into the form${\displaystyle d\cdot 2^s}$ where${\displaystyle d}$ is odd.

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

${\displaystyle U_d\equiv 0(\mathrm{mod}n)}$

or

${\displaystyle V_{d\cdot 2^r}\equiv 0(\mathrm{mod}n)}$

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, thestrong 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${\displaystyle P}$ and${\displaystyle Q}$ be relatively prime positive integers for which${\displaystyle P^2-4Q}$ is positive but not a square. Then there is a positive constant${\displaystyle c}$ (depending on${\displaystyle P}$ and${\displaystyle Q}$) such that the number of strong Lucas pseudoprimes not exceeding${\displaystyle x}$ is greater than${\displaystyle c\cdot \log x}$, for${\displaystyle x}$ sufficiently large.

We can setQ = −1, then${\displaystyle U_n}$ and${\displaystyle V_n}$ areP-Fibonacci sequence andP-Lucas sequence, the pseudoprimes can be calledstrong Lucas pseudoprime in baseP, for example, the least strong Lucas pseudoprime withP = 1, 2, 3, ... are 4181, 169, 119, ...

Anextra strong Lucas pseudoprime^[6][7]is a strong Lucas pseudoprime for a set of parameters (P,Q) whereQ = 1, satisfying one of the conditions

${\displaystyle U_d\equiv 0\text{ and }{V}_d\equiv \pm 2(\mathrm{mod}n)}$

or

${\displaystyle V_{d\cdot 2^r}\equiv 0(\mathrm{mod}n)}$

for some. An extra strong Lucas pseudoprime is also a strong Lucas pseudoprime for the same${\displaystyle (P,Q)}$ pair. No number can be a strong Lucas pseudoprime to more than1⁄4 of all bases, or an extra strong Lucas pseudoprime to more than1⁄8 of all bases.

Before embarking on a probable prime test, one usually verifies thatn, 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 usingNewton's method for square roots.

We choose a Lucas sequence where the Jacobi symbol${\displaystyle \left(\frac{D}{n}\right)=-1}$, so that δ(n) =n + 1.

Givenn, one technique for choosingD is to use trial and error to find the firstD in the sequence 5, −7, 9, −11, ... such that${\displaystyle \left(\frac{D}{n}\right)=-1}$. Note that${\displaystyle \left(\frac{k}{n}\right)\left(\frac{-k}{n}\right)=-1}$.(IfD andn have a prime factor in common, then${\displaystyle \left(\frac{D}{n}\right)=0.}$).With this sequence ofD values, the average number ofD values that must be tried before we encounter one whose Jacobi symbol is −1 is about 1.79.^[1]: 1416Once we haveD, we set${\displaystyle P=1}$ and${\displaystyle Q=(1-D)/4}$.It is a good idea to check thatn has no prime factors in common withP orQ.This method ("Method A") of choosingD,P, andQ was suggested byJohn Selfridge.

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

GivenD,P, andQ, there are recurrence relations that enable us to quickly compute${\displaystyle U_{n+1}}$ and${\displaystyle V_{n+1}}$ in${\displaystyle O({\log }_{2}n)}$ steps; seeLucas sequence § Other relations. To start off,

${\displaystyle U_1=1}$

${\displaystyle V_1=P}$

${\displaystyle Q^1=Q}$

First, we can double the subscript from${\displaystyle k}$ to${\displaystyle 2k}$ in one step using the recurrence relations

${\displaystyle U_{2k}=U_k\cdot V_k,}$

${\displaystyle V_{2k}=V_k^2-2Q^k=\frac{V_k^2+D{U}_k^2}{2},}$

${\displaystyle Q^{2k}=(Q^k{)}^2.}$

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

${\displaystyle U_{2k+1}=(P\cdot U_{2k}+V_{2k})/2,}$

${\displaystyle V_{2k+1}=(D\cdot U_{2k}+P\cdot V_{2k})/2,}$

${\displaystyle Q^{2k+1}=Q\cdot Q^{2k}.}$

At each stage, we reduce all of the variables modulon. When dividing by 2modulon, if the numerator is odd addn (which does not change the value modulon) to make it even before dividing by 2.'

We use the bits of the binary expansion ofn to determinewhich terms in the sequence to compute. For example, ifn+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₂ = 1, 10₂ = 2, 100₂ = 4, 101₂ = 5, 1010₂ = 10, 1011₂ = 11, 10110₂ = 22, 101100₂ = 44. Therefore, we computeU₁,U₂,U₄,U₅,U₁₀,U₁₁,U₂₂, andU₄₄. We also compute the same-numbered terms in theV sequence, along withQ¹,Q²,Q⁴,Q⁵,Q¹⁰,Q¹¹,Q²², andQ⁴⁴.

By the end of the calculation, we will have computedU_n+1,V_n+1, andQⁿ⁺¹, (modn).We then check congruence (2) using our expected value ofU_n+1.

When the parametersD,P, andQ are chosen as described above, the first 10 Lucas pseudoprimes are:^[1]: 1401323, 377, 1159, 1829, 3827, 5459, 5777, 9071, 9179, and 10877 (sequenceA217120 in theOEIS)

Thestrong versions of the Lucas test can be implemented in a similar way. With the same parameters, the first 10strong Lucas pseudoprimes are: 5459, 5777, 10877, 16109, 18971, 22499, 24569, 25199, 40309, and 58519(sequenceA217255 in theOEIS)

Extra strong Lucas pseudoprimes use different parameters: fix${\displaystyle Q=1}$.Then tryP = 3, 4, 5, 6, ..., until a value of${\displaystyle D=P^2-4Q}$ is found so that the Jacobi symbol${\displaystyle \left(\frac{D}{n}\right)=-1}$. The first 10extra strong Lucas pseudoprimes are989, 3239, 5777, 10877, 27971, 29681, 30739, 31631, 39059, and 72389(sequenceA217719 in theOEIS)

If we have checked that congruence (2) is true, there are additional congruence conditions we can check that have almost no additional computational cost. By providing an additional opportunity forn to be proved composite, these increase the reliability of the test.

Ifn is an odd prime and${\displaystyle \left(\frac{D}{n}\right)=-1}$, then we have the following:^{[1]: 1392 Eq. 2}

${\displaystyle V_{n+1}\equiv 2Q(\mathrm{mod}n).}$

3

Although this congruence condition is not part of the Lucas probable prime test proper, it is almost free to check this condition because, as noted above, the easiest way to computeU_n+1 is to computeV_n+1 as well.

If Selfridge's Method A (above) for choosing parameters is modified so that, if it selectsD = 5, it uses the parametersP =Q = 5 rather thanP = 1,Q = −1 (avoidingQ ≠ ±1; "Method A*"), then 913 = 11·83 is theonly composite less than 10⁸ for which congruence (3) is true (see page 1409 and Table 6 of;^[1]). More extensive calculations show that, with this method of choosingD,P, andQ, there are only five odd, composite numbers less than 10¹⁵ for which congruence (3) is true.^[8]

If${\displaystyle Q\ne \pm 1}$ (and GCD(n,Q) = 1), then anEuler–Jacobi probable prime test to the base Q can also be implemented at minor computational cost.

The computation of${\displaystyle V_{n+1}}$ depends on${\displaystyle V_{(n+1)/2}}$ and${\displaystyle Q^{(n+1)/2}}$. This is${\displaystyle Q}$ times${\displaystyle Q^{(n-1)/2}}$, and ifn is prime, then byEuler's criterion,

${\displaystyle Q^{(n-1)/2}\equiv \left(\frac{Q}{n}\right)(\mathrm{mod}n)}$ .

(Here,${\displaystyle \left(\frac{Q}{n}\right)}$ is theLegendre symbol; ifn is prime, this is the same as the Jacobi symbol).

Therefore, ifn is prime, we must have,

${\displaystyle Q^{(n+1)/2}\equiv Q\cdot Q^{(n-1)/2}\equiv Q\cdot \left(\frac{Q}{n}\right)(\mathrm{mod}n).}$

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

There is one more congruence condition on${\displaystyle U_n}$ and${\displaystyle V_n}$ which must be true ifn is prime and can be checked.^[1]: §2,6

k applications of theMiller–Rabin primality test declare a compositen 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.^[9]

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

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

There are two trivial exceptions. One isn = 9. The other is whenn =p(p+2) is the product of twotwin primes. Such ann is easy to factor, because in this case,n+1 = (p+1)² is a perfect square. One can quickly detect perfect squares usingNewton's method for square roots.

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

WhenP = 1 andQ = −1, theU_n(P,Q) sequence represents the Fibonacci numbers.

AFibonacci pseudoprime is often^{[2]: 264,  [3]: 142,  [4]: 127}defined as a composite numbern not divisible by 5 for which congruence (1) holds withP = 1 andQ = −1. By this definition, the Fibonacci pseudoprimes form a sequence:

323, 377, 1891, 3827, 4181, 5777, 6601, 6721, 8149, 10877, ... (sequenceA081264 in theOEIS).

The references of Anderson and Jacobsen below use this definition.

Ifn 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 aFermat pseudoprime base 2. However, whenn is congruent to 1 or 4 modulo 5, the opposite is true, with over 12% of Fibonacci pseudoprimes under 10¹¹ also being base-2 Fermat pseudoprimes.

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

${\displaystyle V_n(P,Q)\equiv P(\mathrm{mod}n).}$

5

This leads to an alternative definition of Fibonacci pseudoprime:^[10][11]

aFibonacci pseudoprime is a composite numbern for which congruence (5) holds withP = 1 andQ = −1.

This definition leads the Fibonacci pseudoprimes form a sequence:

705, 2465, 2737, 3745, 4181, 5777, 6721, 10877, 13201, 15251, ... (sequenceA005845 in theOEIS),

which are also referred to asBruckman-Lucas pseudoprimes.^[4]: 129Hoggatt and Bicknell studied properties of these pseudoprimes in 1974.^[12] Singmaster computed these pseudoprimes up to 100000.^[13] Jacobsen lists all 111443 of these pseudoprimes less than 10¹³.^[14]

It has been shown that there are no even Fibonacci pseudoprimes as defined by equation (5).^[15][16] However, even Fibonacci pseudoprimes do exist (sequenceA141137 in theOEIS) under the first definition given by (1).

Astrong Fibonacci pseudoprime is a composite numbern for which congruence (5) holds forQ = −1 and allP.^[17] It follows^[17]: 460 that an odd composite integern is a strong Fibonacci pseudoprime if and only if:

1. n is aCarmichael number
2. 2(p + 1) | (n − 1) or 2(p + 1) | (n −p) for every primep dividingn.

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

APell pseudoprime may be defined as a composite numbern for which equation (1) above is true withP = 2 andQ = −1; the sequenceU_n then being thePell sequence. The first pseudoprimes are then 35, 169, 385, 779, 899, 961, 1121, 1189, 2419, ...

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

${\displaystyle U_n\equiv \left(\frac{2}{n}\right)(\mathrm{mod}n)}$

with (P,Q) = (2, −1) again definingU_n as thePell 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, ...

• Anderson, Peter G.Fibonacci Pseudoprimes, their factors, and their entry points.
• Anderson, Peter G.Fibonacci Pseudoprimes under 2,217,967,487 and their factors.
• Jacobsen, DanaPseudoprime Statistics, Tables, and Data (data for Lucas, Strong Lucas, AES Lucas, ES Lucas pseudoprimes below 10¹⁴; Fibonacci and Pell pseudoprimes below 10¹²)
• Weisstein, Eric W."Fibonacci Pseudoprime".MathWorld.
• Weisstein, Eric W."Lucas Pseudoprime".MathWorld.
• Weisstein, Eric W."Strong Lucas Pseudoprime".MathWorld.
• Weisstein, Eric W."Extra Strong Lucas Pseudoprime".MathWorld.

• Fibonacci numbers
• Pseudoprimes

• Articles with short description
• Short description matches Wikidata