Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Lucas pseudoprimes

Authors: Robert Baillie and Samuel S. Wagstaff
Journal: Math. Comp. 35 (1980), 1391-1417
MSC: Primary 10A25
MathSciNet review: 583518
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 10A25

Retrieve articles in all journals with MSC: 10A25

Additional Information

Keywords: Pseudoprime, Lucas sequence, Lucas pseudoprime, strong pseudoprime, Euler pseudoprime, primality testing
Article copyright: © Copyright 1980 American Mathematical Society