Lucas Pseudoprime - Lucas Pseudoprimes

Lucas Pseudoprimes

A Lucas pseudoprime is a composite number n for which n is a factor of U_n-ε. (Riesel adds the condition that the Jacobi symbol should be −1.)

In the specific case of the Fibonacci sequence, where P = 1, Q = -1 and D = 5, the first Lucas pseudoprimes are 323 and 377; and are both −1, the 324th Fibonacci number is a multiple of 323, and the 378th is a multiple of 377.

A strong Lucas pseudoprime is an odd composite number n with (n,D)=1, and n-ε=2rs with s odd, satisfying one of the conditions

n divides U_s

n divides V_2js

for some j < r. A strong Lucas pseudoprime is also a Lucas pseudoprime.

An extra strong Lucas pseudoprime is a strong Lucas pseudoprime for a set of parameters (P,Q) where Q = 1, satisfying one of slightly modified conditions

n divides U_s and V_s is congruent to ±2 modulo n

n divides V_2js

for some j < r. An extra strong Lucas pseudoprime is also a strong Lucas pseudoprime.

By combining a Lucas pseudoprime test with a Fermat primality test, say, to base 2, one can obtain very powerful probabilistic tests for primality. See the paper by Baillie and Wagstaff, and the books by Crandall and Riesel.