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.109, 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.)

Enter n:

Last modified 18th March 2004
Return to main page