Strong Lucas Pseudoprime

Let $U(P,Q)$ and $V(P,Q)$ be Lucas Sequences generated by $P$ and $Q$, and define

$$D\equiv P^2-4Q.$$

Let $n$ be an Odd Composite Number with $(n,D)=1$, and $n-(D/n)=2^s d$ with $d$ Odd and $s\geq 0$, where $(a/b)$ is the Legendre Symbol. If

$$U_d\equiv 0\ \left({{\rm mod\ } {n}}\right)$$

or

$$V_{2^rd}\equiv 0\ \left({{\rm mod\ } {n}}\right)$$

for some $r$ with $0\leq r<s$, then $n$ is called a strong Lucas pseudoprime with parameters $(P,Q)$.

A strong Lucas pseudoprime is a Lucas Pseudoprime to the same base. Arnault (1997) showed that any Composite Number $n$ is a strong Lucas pseudoprime for at most 4/15 of possible bases (unless $n$ is the Product of Twin Primes having certain properties).

See also Extra Strong Lucas Pseudoprime, Lucas Pseudoprime

References

Arnault, F. ``The Rabin-Monier Theorem for Lucas Pseudoprimes.'' Math. Comput. 66, 869-881, 1997.

Ribenboim, P. ``Euler-Lucas Pseudoprimes (elpsp($P,Q$)) and Strong Lucas Pseudoprimes (slpsp($P,Q$)).'' §2.X.C in The New Book of Prime Number Records, 3rd ed. New York: Springer-Verlag, pp. 130-131, 1996.