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 , 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.

**[1]**John Brillhart, D. H. Lehmer, and J. L. Selfridge,*New primality criteria and factorizations of 2^{𝑚}±1*, Math. Comp.**29**(1975), 620–647. MR**0384673**, 10.1090/S0025-5718-1975-0384673-1**[2]**DOV JARDEN,*Recurring Sequences*, 3rd ed., Riveon Lemathematika, Jerusalem, 1973, pp. 41-59.**[3]**A. O. L. Atkin and B. J. Birch (eds.),*Computers in number theory*, Academic Press, London-New York, 1971. MR**0314733****[4]**D. H. LEHMER, "Use of Pierce functions for a primality test." (Unpublished notes.)**[5]**Emma Lehmer,*Criteria for cubic and quartic residuacity*, Mathematika**5**(1958), 20–29. MR**0095162****[6]**Tracy A. Pierce,*The numerical factors of the arithmetic forms ∑ᵢ₌₁ⁿ(1±𝛼ᵢ^{𝑚})*, Ann. of Math. (2)**18**(1916), no. 2, 53–64. MR**1503584**, 10.2307/2007169**[7]**J. M. Pollard,*Theorems on factorization and primality testing*, Proc. Cambridge Philos. Soc.**76**(1974), 521–528. MR**0354514****[8]**J. L. Selfridge and M. C. Wunderlich,*An efficient algorithm for testing large numbers for primality*, Proceedings of the Fourth Manitoba Conference on Numerical Mathematics (Winnipeg, Man., 1974) Utilitas Math., Winnipeg, Man., 1975, pp. 109–120. Congr. Numer., No. XII. MR**0369226****[9]**H. C. Williams,*A generalization of Lehmer’s functions*, Acta Arith.**29**(1976), no. 4, 315–341. MR**0412091****[10]**H. C. Williams and J. S. Judd,*Determination of the primality of 𝑁 by using factors of 𝑁²±1*, Math. Comp.**30**(1976), no. 133, 157–172. MR**0396390**, 10.1090/S0025-5718-1976-0396390-3**[11]**M. C. WUNDERLICH & J. L. SELFRIDGE, "A design for a number theory package with an optimized trial division routine,"*Comm. ACM*, v. 17, 1974, pp. 272-276.

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

Keywords:
Primality testing,
generalized Lehmer functions,
Fibonacci numbers,
Lucas numbers

Article copyright:
© Copyright 1976
American Mathematical Society