Classical Primality and Factoring
Lucas Sequences and Lucas Pseudoprimes
Lucas sequences, the Lucas probable prime test, and why it complements the strong pseudoprime test rather than duplicating it.
Engineering / MathematicsClassical Primality and Factoring2 min readKV-MATH-0648
Lucas sequences give a primality test based on a quadratic recurrence rather than on modular exponentiation. Its failure modes are different from those of the strong test, which is what makes the combination valuable.
Lucas sequences
Given parameters defining a quadratic, two integer sequences satisfy the associated linear recurrence. The Fibonacci numbers are the simplest instance.
The test
For a prime not dividing the discriminant, a specific term of the sequence must vanish modulo that prime, with the index determined by the Jacobi symbol of the discriminant.
Why it complements the strong test
| Test | Works in | Failure mode |
|---|---|---|
| Strong pseudoprime | The multiplicative group modulo n | Composites with particular multiplicative structure |
| Lucas | A quadratic extension | Composites with particular quadratic structure |
Parameter selection
The parameters must be chosen so the discriminant is a non-residue modulo the candidate. Selmer's method scans a fixed sequence of candidate discriminants and takes the first with Jacobi symbol minus one.
Strong Lucas test
As with the Fermat test, a strong version exists that additionally examines the sequence of intermediate values. It is stronger and costs little more, and it is what Baillie-PSW actually uses.
Cost
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 8.3. Structural reference unverified: the source file was not available during authoring; chapter and section numbers are taken from the published edition and have not been checked against a physical copy.