Remote Access Mathematics of Computation
Green Open Access

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

Keywords: Primality testing, generalized Lehmer functions, Fibonacci numbers, Lucas numbers
Article copyright: © Copyright 1976 American Mathematical Society