Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
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

DOI: http://dx.doi.org/10.1090/S0025-5718-1980-0583518-6
PII: S 0025-5718(1980)0583518-6
Keywords: Pseudoprime, Lucas sequence, Lucas pseudoprime, strong pseudoprime, Euler pseudoprime, primality testing
Article copyright: © Copyright 1980 American Mathematical Society