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 <italic>n</italic> with respect to which <italic>n</italic> 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 <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="f left-parenthesis n right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>f</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">f(n)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> for which the Jacobi symbol <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="left-parenthesis f left-parenthesis n right-parenthesis slash n right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>f</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">(f(n)/n)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is less than 1, we evaluate the average order of the function <italic>f</italic> .