Determination of the primality of by using factors of
Authors:
H. C. Williams and J. S. Judd
Journal:
Math. Comp. 30 (1976), 157172
MSC:
Primary 10A25
MathSciNet review:
0396390
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: Algorithms are developed which can be used to determine the primality of a large integer N when a sufficient number of prime factors of are known. A test for the primality of N which makes use of known factors of and and the factor bounds on these numbers is also presented. In order to develop the necessary theory, the properties of some functions which are a generalization of Lehmer functions are used. Several examples of numbers proved prime by employing these tests are given.
 [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]
D.
H. Lehmer, Computer technology applied to the theory of
numbers, Studies in Number Theory, Math. Assoc. Amer. (distributed by
PrenticeHall, Englewood Cliffs, N.J.), 1969, pp. 117–151. MR 0246815
(40 #84)
 [4]
Michael
A. Morrison, A note on primality testing using
Lucas sequences, Math. Comp. 29 (1975), 181–182.
Collection of articles dedicated to Derrick Henry Lehmer on the occasion of
his seventieth birthday. MR 0369234
(51 #5469), http://dx.doi.org/10.1090/S00255718197503692342
 [5]
J.
M. Pollard, Theorems on factorization and primality testing,
Proc. Cambridge Philos. Soc. 76 (1974), 521–528. MR 0354514
(50 #6992)
 [6]
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)
 [7]
H. C. WILLIAMS, "A generalization of Lehmer's functions," Acta Arith. (To appear).
 [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, "Computer technology applied to the theory of numbers," Studies in Number Theory, Math. Assoc. Amer.; distributed by PrenticeHall, Englewood Cliffs, N. J., 1969, pp. 117151. MR 40 #84. MR 0246815 (40:84)
 [4]
 M. A. MORRISON, "A note on primality testing using Lucas sequences," Math. Comp., v. 29, 1975, pp. 181182. MR 0369234 (51:5469)
 [5]
 J. M. POLLARD, "Theorems on factorization and primality testing," Proc. Cambridge Philos. Soc., v. 76, 1974, pp. 521528. MR 0354514 (50:6992)
 [6]
 J. L. SELFRIDGE & M. C. WUNDERLICH, "An efficient algorithm for testing large numbers for primality," Proc. Fourth Manitoba Conf. on Numerical Math., Winnipeg, Manitoba, 1974, pp. 109120. MR 0369226 (51:5461)
 [7]
 H. C. WILLIAMS, "A generalization of Lehmer's functions," Acta Arith. (To appear).
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
10A25
Retrieve articles in all journals
with MSC:
10A25
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718197603963903
PII:
S 00255718(1976)03963903
Keywords:
Primality testing,
Lucas functions,
Lehmer functions
Article copyright:
© Copyright 1976
American Mathematical Society
