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)

 

Some algorithms for prime testing using generalized Lehmer functions


Authors: H. C. Williams and J. S. Judd
Journal: Math. Comp. 30 (1976), 867-886
MSC: Primary 10A25; Secondary 10-04
MathSciNet review: 0414473
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Let N be an odd integer thought to be prime. The properties of special functions which are generalizations of the functions of Lehmer (Ann. of Math., v. 31, 1930, pp. 419-448) are used to develop algorithms that produce information concerning the possible prime divisors of N. It is shown how the factors of $ N \pm 1,{N^2} + 1,{N^2} \pm N + 1$, together with the factor bounds on these numbers, may all be used to calculate lower bounds for the possible prime divisors of N. Frequently, these bounds are large enough that N may be shown to be prime.

These tests were implemented on an IBM/370-158 computer and run on the pseudoprime divisors of the first 385 Fibonacci and Lucas numbers.


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


Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 10A25, 10-04

Retrieve articles in all journals with MSC: 10A25, 10-04


Additional Information

DOI: http://dx.doi.org/10.1090/S0025-5718-1976-0414473-6
PII: S 0025-5718(1976)0414473-6
Keywords: Primality testing, generalized Lehmer functions, Fibonacci numbers, Lucas numbers
Article copyright: © Copyright 1976 American Mathematical Society