|
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
(52 #5546), http://dx.doi.org/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, 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, (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/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.
- [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.
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
|
