### The Lucas-strong base 2 pseudoprime test

Here n is odd and n > 1.

If 1 is returned, then n is a strong base 2 pseudoprime and a Lucas probable prime.

If 0 is returned, then n is composite.
(See C. Pomerance, J.L. Selfridge, S. Wagstaff Jr., *The Pseudoprimes to 25.10*^{9},
Mathematics of computation, 35 (1980) 1003-1026.

At the end of this paper it is conjectured that
if n is a strong base 2 pseudoprime and a Lucas
probable prime, then n is in fact a prime, though this is unlikely to be always the case. A prize is offered for a counterexample.)

*Last modified 18th March 2004*

Return to main page