Lucas pseudoprime
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.
BaillieWagstaffLucas pseudoprimes
Baillie and Wagstaff define Lucas pseudoprimes as follows:^{[1]} Given integers P and Q, where P > 0 and [math]\displaystyle{ D=P^24Q }[/math], let U_{k}(P, Q) and V_{k}(P, Q) be the corresponding Lucas sequences.
Let n be a positive integer and let [math]\displaystyle{ \left(\tfrac{D}{n}\right) }[/math] be the Jacobi symbol. We define
 [math]\displaystyle{ \delta(n)=n\left(\tfrac{D}{n}\right). }[/math]
If n is a prime that does not divide Q, then the following congruence condition holds:

[math]\displaystyle{ U_{\delta(n)} \equiv 0 \pmod {n}. }[/math]
(
)
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 BaillieWagstaffLucas 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]}
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,^{[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 [math]\displaystyle{ \left(\tfrac{D}{n}\right) }[/math] 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 [math]\displaystyle{ \left(\tfrac{D}{n}\right)=1, }[/math] then equation (1) becomes

[math]\displaystyle{ U_{n+1} \equiv 0 \pmod {n}. }[/math]
(
)
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, U_{1} = 1, U_{2} = 3, U_{3} = 10, etc.
First, let n = 19. The Jacobi symbol [math]\displaystyle{ \left(\tfrac{13}{19}\right) }[/math] is −1, so δ(n) = 20, U_{20} = 6616217487 = 19·348221973 and we have
 [math]\displaystyle{ U_{20} = 6616217487 \equiv 0 \pmod {19} . }[/math]
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 [math]\displaystyle{ \left(\tfrac{13}{119}\right) }[/math] = −1, and we can compute
 [math]\displaystyle{ U_{120} \equiv 0 \pmod {119}. }[/math]
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, ...
Strong Lucas pseudoprimes
Now, factor [math]\displaystyle{ \delta(n)=n\left(\tfrac{D}{n}\right) }[/math] into the form [math]\displaystyle{ d\cdot2^s }[/math] where [math]\displaystyle{ d }[/math] 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
 [math]\displaystyle{ U_d \equiv 0 \pmod {n} }[/math]
or
 [math]\displaystyle{ V_{d \cdot 2^r} \equiv 0 \pmod {n} }[/math]
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 [math]\displaystyle{ P }[/math] and [math]\displaystyle{ Q }[/math] be relatively prime positive integers for which [math]\displaystyle{ P^2  4Q }[/math] is positive but not a square. Then there is a positive constant [math]\displaystyle{ c }[/math] (depending on [math]\displaystyle{ P }[/math] and [math]\displaystyle{ Q }[/math]) such that the number of strong Lucas pseudoprimes not exceeding [math]\displaystyle{ x }[/math] is greater than [math]\displaystyle{ c \cdot \log x }[/math], for [math]\displaystyle{ x }[/math] sufficiently large.
We can set Q = −1, then [math]\displaystyle{ U_n }[/math] and [math]\displaystyle{ V_n }[/math] are PFibonacci sequence and PLucas sequence, the pseudoprimes can be called strong Lucas pseudoprime in base P, for example, the least strong Lucas pseudoprime with P = 1, 2, 3, ... are 4181, 169, 119, ...
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
 [math]\displaystyle{ U_d \equiv 0 \pmod {n} \text{ and } V_d \equiv \pm 2 \pmod {n} }[/math]
or
 [math]\displaystyle{ V_{d \cdot 2^r} \equiv 0 \pmod {n} }[/math]
for some [math]\displaystyle{ 0 \le r\lt s1 }[/math]. An extra strong Lucas pseudoprime is also a strong Lucas pseudoprime for the same [math]\displaystyle{ (P,Q) }[/math] pair.
Implementing a Lucas probable prime test
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 [math]\displaystyle{ \left(\tfrac{D}{n}\right)=1 }[/math], 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 [math]\displaystyle{ \left(\tfrac{D}{n}\right)=1 }[/math]. Note that [math]\displaystyle{ \left(\tfrac{k}{n}\right)\left(\tfrac{k}{n}\right)=1 }[/math]. (If D and n have a prime factor in common, then [math]\displaystyle{ \left(\tfrac{D}{n}\right)=0 }[/math]). 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 [math]\displaystyle{ P=1 }[/math] and [math]\displaystyle{ Q=(1D)/4 }[/math]. 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 [math]\displaystyle{ U_{n+1} }[/math] and [math]\displaystyle{ V_{n+1} }[/math] in [math]\displaystyle{ O(\log_2 n) }[/math] steps; see Lucas sequence § Other relations. To start off,
 [math]\displaystyle{ U_{1}=1 }[/math]
 [math]\displaystyle{ V_{1}=P=1 }[/math]
First, we can double the subscript from [math]\displaystyle{ k }[/math] to [math]\displaystyle{ 2k }[/math] in one step using the recurrence relations
 [math]\displaystyle{ U_{2k}=U_k\cdot V_k }[/math]
 [math]\displaystyle{ V_{2k}=V_k^22Q^k=\frac{V_k^2+DU_k^2}{2} }[/math].
Next, we can increase the subscript by 1 using the recurrences
 [math]\displaystyle{ U_{2k+1}=(P\cdot U_{2k}+V_{2k})/2 }[/math]
 [math]\displaystyle{ V_{2k+1}=(D\cdot U_{2k}+P\cdot V_{2k})/2 }[/math].
If [math]\displaystyle{ P\cdot U_{2k}+V_{2k} }[/math] is odd, replace it with [math]\displaystyle{ P\cdot U_{2k}+V_{2k}+n }[/math]; this is even so it can now be divided by 2. The numerator of [math]\displaystyle{ V_{2k+1} }[/math] 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 [math]\displaystyle{ U }[/math], [math]\displaystyle{ V }[/math], and the power of [math]\displaystyle{ Q }[/math], 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 samenumbered 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}, V_{n+1}, and Q^{n+1}, (mod n). We then check congruence (2) using our known value of 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 [math]\displaystyle{ Q = 1 }[/math]. Then try P = 3, 4, 5, 6, ..., until a value of [math]\displaystyle{ D=P^24Q }[/math] is found so that the Jacobi symbol [math]\displaystyle{ \left(\tfrac{D}{n}\right)=1 }[/math]. 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)
Checking additional congruence conditions
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 [math]\displaystyle{ \left(\tfrac{D}{n}\right)=1 }[/math], then we have the following (see equation 2 on page 1392 of ^{[1]}):

[math]\displaystyle{ V_{n+1} \equiv 2 Q \pmod {n} . }[/math]
(
)
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 U_{n+1}.
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 [math]\displaystyle{ \left(\tfrac{D}{n}\right) }[/math] remain unchanged and P = Q = 5 (see Lucas sequenceAlgebraic 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 [math]\displaystyle{ Q \neq \pm 1 }[/math], then a further congruence condition that involves very little additional computation can be implemented.
Recall that [math]\displaystyle{ Q^{n+1} }[/math] is computed during the calculation of [math]\displaystyle{ U_{n+1} }[/math], and we can easily save the previously computed power of [math]\displaystyle{ Q }[/math], namely, [math]\displaystyle{ Q^{(n+1)/2} }[/math].
If n is prime, then, by Euler's criterion,
 [math]\displaystyle{ Q^{(n1)/2} \equiv \left(\tfrac{Q}{n}\right) \pmod {n} }[/math] .
(Here, [math]\displaystyle{ \left(\tfrac{Q}{n}\right) }[/math] is the Legendre symbol; if n is prime, this is the same as the Jacobi symbol).
Therefore, if n is prime, we must have,

[math]\displaystyle{ Q^{(n+1)/2} \equiv Q \cdot Q^{(n1)/2} \equiv Q \cdot \left(\tfrac{Q}{n}\right) \pmod {n} . }[/math]
(
)
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.
Comparison with the Miller–Rabin primality test
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.
Fibonacci pseudoprimes
When P = 1 and Q = −1, the U_{n}(P,Q) sequence represents the Fibonacci numbers.
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:
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 base2 Fermat pseudoprimes.
If n is prime and GCD(n, Q) = 1, then we also have^{[1]}^{:1392}

[math]\displaystyle{ V_n(P,Q) \equiv P \pmod{n}. }[/math]
(
)
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:
which are also referred to as BruckmanLucas 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.
Pell pseudoprimes
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:
 [math]\displaystyle{ \text{ } U_n \equiv \left(\tfrac{2}{n}\right) \pmod {n} }[/math]
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, ...
References
 ↑ ^{1.00} ^{1.01} ^{1.02} ^{1.03} ^{1.04} ^{1.05} ^{1.06} ^{1.07} ^{1.08} ^{1.09} ^{1.10} ^{1.11} ^{1.12} ^{1.13} Robert Baillie; Samuel S. Wagstaff, Jr. (October 1980). "Lucas Pseudoprimes". Mathematics of Computation 35 (152): 1391–1417. doi:10.1090/S00255718198005835186. http://mpqs.free.fr/LucasPseudoprimes.pdf.
 ↑ ^{2.0} ^{2.1} ^{2.2} ^{2.3} David Bressoud; Stan Wagon (2000). A Course in Computational Number Theory. New York: Key College Publishing in cooperation with Springer. ISBN 9781930190108. https://archive.org/details/courseincomputat0000bres.
 ↑ ^{3.0} ^{3.1} ^{3.2} Richard E. Crandall; Carl Pomerance (2005). Prime numbers: A computational perspective (2nd ed.). SpringerVerlag. ISBN 0387252827.
 ↑ ^{4.0} ^{4.1} ^{4.2} Paulo Ribenboim (1996). The New Book of Prime Number Records. SpringerVerlag. ISBN 0387944575.
 ↑ Carl Pomerance; John L. Selfridge; Samuel S. Wagstaff, Jr. (July 1980). "The pseudoprimes to 25·10^{9}". Mathematics of Computation 35 (151): 1003–1026. doi:10.1090/S00255718198005728727. //math.dartmouth.edu/~carlp/PDF/paper25.pdf.
 ↑ Jon Grantham (2001). "Frobenius Pseudoprimes". Mathematics of Computation 70 (234): 873–891. doi:10.1090/S0025571800011972. Bibcode: 2001MaCom..70..873G.
 ↑ Robert Baillie; Andrew Fiori; Samuel S. Wagstaff, Jr. (July 2021). "Strengthening the BailliePSW Primality Test". Mathematics of Computation 90 (330): 1931–1955. doi:10.1090/mcom/3616.
 ↑ F. Arnault (April 1997). "The RabinMonier Theorem for Lucas Pseudoprimes". Mathematics of Computation 66 (218): 869–881. doi:10.1090/s0025571897008363.
 ↑ Adina Di Porto; Piero Filipponi (1989). "More on the Fibonacci Pseudoprimes". Fibonacci Quarterly 27 (3): 232–242. https://www.fq.math.ca/Issues/273.pdf.
 ↑ Di Porto, Adina; Filipponi, Piero; Montolivo, Emilio (1990). "On the generalized Fibonacci pseudoprimes". Fibonacci Quarterly 28: 347–354.
 ↑ V. E. Hoggatt, Jr.; Marjorie Bicknell (September 1974). "Some Congruences of the Fibonacci Numbers Modulo a Prime p". Mathematics Magazine 47 (4): 210–214. doi:10.2307/2689212.
 ↑ David Singmaster (1983). "Some Lucas Pseudoprimes". Abstracts Amer. Math. Soc. 4 (83T–10–146): 197.
 ↑ "Pseudoprime Statistics and Tables". http://ntheory.org/pseudoprimes.html.
 ↑ P. S. Bruckman (1994). "Lucas Pseudoprimes are odd". Fibonacci Quarterly 32: 155–157.
 ↑ Di Porto, Adina (1993). "Nonexistence of Even Fibonacci Pseudoprimes of the First Kind". Fibonacci Quarterly 31: 173–177.
 ↑ ^{16.0} ^{16.1} Müller, Winfried B.; Oswald, Alan (1993). "Generalized Fibonacci Pseudoprimes and Probable Primes". in G.E. Bergum. 5. Kluwer. pp. 459–464. doi:10.1007/9789401120586_45.
External links
 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, Dana Pseudoprime Statistics, Tables, and Data (data for Lucas, Strong Lucas, AES Lucas, ES Lucas pseudoprimes below 10^{14}; Fibonacci and Pell pseudoprimes below 10^{12})
 Weisstein, Eric W.. "Fibonacci Pseudoprime". http://mathworld.wolfram.com/FibonacciPseudoprime.html.
 Weisstein, Eric W.. "Lucas Pseudoprime". http://mathworld.wolfram.com/LucasPseudoprime.html.
 Weisstein, Eric W.. "Strong Lucas Pseudoprime". http://mathworld.wolfram.com/StrongLucasPseudoprime.html.
 Weisstein, Eric W.. "Extra Strong Lucas Pseudoprime". http://mathworld.wolfram.com/ExtraStrongLucasPseudoprime.html.
Original source: https://en.wikipedia.org/wiki/Lucas pseudoprime.
Read more 