Some algorithms for prime testing using generalized Lehmer functions
Authors:
H. C. Williams and J. S. Judd
Journal:
Math. Comp. 30 (1976), 867886
MSC:
Primary 10A25; Secondary 1004
MathSciNet review:
0414473
Fulltext 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. 419448) 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/370158 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
(52 #5546), http://dx.doi.org/10.1090/S00255718197503846731
 [2]
DOV JARDEN, Recurring Sequences, 3rd ed., Riveon Lemathematika, Jerusalem, 1973, pp. 4159.
 [3]
A.
O. L. Atkin and B.
J. Birch (eds.), Computers in number theory, Academic Press,
LondonNew York, 1971. 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 5 (1958), 20–29. MR 0095162
(20 #1668)
 [6]
Tracy
A. Pierce, The numerical factors of the arithmetic forms
∑ᵢ₌₁ⁿ(1±𝛼ᵢ^{𝑚}),
Ann. of Math. (2) 18 (1916), no. 2, 53–64. MR
1503584, http://dx.doi.org/10.2307/2007169
 [7]
J.
M. Pollard, Theorems on factorization and primality testing,
Proc. Cambridge Philos. Soc. 76 (1974), 521–528. MR 0354514
(50 #6992)
 [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
(51 #5461)
 [9]
H.
C. Williams, A generalization of Lehmer’s functions,
Acta Arith. 29 (1976), no. 4, 315–341. MR 0412091
(54 #220)
 [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
(53 #257), http://dx.doi.org/10.1090/S00255718197603963903
 [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. 272276.
 [1]
 JOHN BRILLHART, D. H. LEHMER & J. L. SELFRIDGE, "New primality criteria and factorizations of ," Math. Comp., v. 29, 1975, pp. 620647. MR 0384673 (52:5546)
 [2]
 DOV JARDEN, Recurring Sequences, 3rd ed., Riveon Lemathematika, Jerusalem, 1973, pp. 4159.
 [3]
 D. H. LEHMER, "The economics of number theoretic computation," Computers in Number Theory, Academic Press, London and New York, 1971, pp. 19. 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. 2029. 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. 5364. MR 1503584
 [7]
 J. M. POLLARD, "Theorems on factorization and primality testing," Proc. Cambridge Philos. Soc., v. 76, 1974, pp. 521528. 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. 109120. MR 51 #5461. MR 0369226 (51:5461)
 [9]
 H. C. WILLIAMS, "A generalization of Lehmer's functions," Acta Arith., v. 29, 1976, pp. 315341. 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. 157172. 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. 272276.
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
10A25,
1004
Retrieve articles in all journals
with MSC:
10A25,
1004
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718197604144736
PII:
S 00255718(1976)04144736
Keywords:
Primality testing,
generalized Lehmer functions,
Fibonacci numbers,
Lucas numbers
Article copyright:
© Copyright 1976
American Mathematical Society
