Lucas Pseudoprimes

Abstract

We define several types of pseudoprimes with respect to Lucas sequences and prove the analogs of various theorems about ordinary pseudoprimes. For example, we show that Lucas pseudoprimes are rare and we count the Lucas sequences modulo n with respect to which n is a Lucas pseudoprime. We suggest some powerful new primality tests which combine Lucas pseudoprimes with ordinary pseudoprimes. Since these tests require the evaluation of the least number $f(n)$ for which the Jacobi symbol $(f(n)/n)$ is less than 1, we evaluate the average order of the function f.