info prev up next book cdrom email home

Extra Strong Lucas Pseudoprime

Given the Lucas Sequence $U_n(b,-1)$ and $V_n(b,-1)$, define $\Delta=b^2-4$. Then an extra strong Lucas pseudoprime to the base $b$ is a Composite Number $n=2^r s+(\Delta/n)$, where $s$ is Odd and $(n,2\Delta)=1$ such that either $U_s\equiv 0\ \left({{\rm mod\ } {n}}\right)$ and $V_s\equiv \pm 2\ \left({{\rm mod\ } {n}}\right)$, or $V_{2^t s}\equiv 0\ \left({{\rm mod\ } {n}}\right)$ for some $t$ with $0\leq t<r-1$. An extra strong Lucas pseudoprime is a Strong Lucas Pseudoprime with parameters $(b, -1)$. Composite $n$ are extra strong pseudoprimes for at most 1/8 of possible bases (Grantham 1997).

See also Lucas Pseudoprime, Strong Lucas Pseudoprime


Grantham, J. ``Frobenius Pseudoprimes.''

Grantham, J. ``A Frobenius Probable Prime Test with High Confidence.'' 1997.

Jones, J. P. and Mo, Z. ``A New Primality Test Using Lucas Sequences.'' Preprint.

© 1996-9 Eric W. Weisstein