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

DOI:
https://doi.org/10.1090/S0025-5718-1976-0414473-6

MathSciNet review:
0414473

Full-text PDF

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 & J. L. SELFRIDGE, "New primality criteria and factorizations of ,"*Math. Comp.*, v. 29, 1975, pp. 620-647. MR**0384673 (52:5546)****[2]**DOV JARDEN,*Recurring Sequences*, 3rd ed., Riveon Lemathematika, Jerusalem, 1973, pp. 41-59.**[3]**D. H. LEHMER, "The economics of number theoretic computation,"*Computers in Number Theory*, Academic Press, London and New York, 1971, pp. 1-9. MR**47**#3285. MR**0314733 (47:3285)****[4]**D. H. LEHMER, "Use of Pierce functions for a primality test." (Unpublished notes.)**[5]**EMMA LEHMER, "Criteria for cubic and quartic residuacity,"*Mathematika*, v. 5, 1958, pp. 20-29. MR**20**#1668. MR**0095162 (20:1668)****[6]**T. A. PIERCE, "The numerical factors of the arithmetic forms ,"*Ann. of Math.*(2), v. 18, 1916, pp. 53-64. MR**1503584****[7]**J. M. POLLARD, "Theorems on factorization and primality testing,"*Proc. Cambridge Philos. Soc.*, v. 76, 1974, pp. 521-528. MR**50**#6992. MR**0354514 (50:6992)****[8]**J. L. SELFRIDGE & M. C. WUNDERLICH, "An efficient algorithm for testing large numbers for primality,"*Proc. Fourth Manitoba Conf. on Numerical Math.*(Winnipeg, Man.,1974), Congr. Numer., No. 12, Utilitas Math., Winnipeg, Man., 1975, pp. 109-120. MR**51**#5461. MR**0369226 (51:5461)****[9]**H. C. WILLIAMS, "A generalization of Lehmer's functions,"*Acta Arith.*, v. 29, 1976, pp. 315-341. MR**0412091 (54:220)****[10]**H. C. WILLIAMS & J. S. JUDD, "Determination of the primality of*N*by using factors of ,"*Math. Comp.*, v. 30, 1976, pp. 157-172. MR**0396390 (53:257)****[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:
https://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