Some observations on primality testing
Authors:
H. C. Williams and R. Holte
Journal:
Math. Comp. 32 (1978), 905917
MSC:
Primary 10A25; Secondary 1004
MathSciNet review:
0476625
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: Let N be an integer which is to be tested for primality. Previous methods of ascertaining the primality of N make use of factors of , , and in order to increase the size of any possible prime divisor of N until it is impossible for N to be the product of two or more primes. These methods usually 2 work as long as , where K is of the product of the known prime power factors of , , and . In this paper a technique is described which, when used in conjunction with these methods, will often determine the pri mality of N when and l is small.
 [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]
Gary
L. Miller, Riemann’s hypothesis and tests for primality,
J. Comput. System Sci. 13 (1976), no. 3,
300–317. Working papers presented at the ACMSIGACT Symposium on the
Theory of Computing (Albuquerque, N.M., 1975). MR 0480295
(58 #470a)
 [3]
Noel
B. Slater, Gaps and steps for the sequence
𝑛𝜃𝑚𝑜𝑑1, Proc. Cambridge
Philos. Soc. 63 (1967), 1115–1123. MR 0217019
(36 #114)
 [4]
R.
Solovay and V.
Strassen, A fast MonteCarlo test for primality, SIAM J.
Comput. 6 (1977), no. 1, 84–85. MR 0429721
(55 #2732)
 [5]
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
 [6]
H.
C. Williams and J.
S. Judd, Some algorithms for prime testing
using generalized Lehmer functions, Math.
Comp. 30 (1976), no. 136, 867–886. MR 0414473
(54 #2574), http://dx.doi.org/10.1090/S00255718197604144736
 [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]
 GARY L. MILLER, "Riemann's hypothesis and tests for primality," J. Comput. System Sci., v. 13, 1976, pp. 300317. MR 0480295 (58:470a)
 [3]
 NOEL B. SLATER, "Gaps and steps for the sequence ," Proc. Cambridge Philos. Soc., v. 63, 1967, pp. 11151123. MR 0217019 (36:114)
 [4]
 R. SOLOVAY & V. STRASSEN, "A fast MonteCarlo test for primality," SIAM J. Comput., v. 6, 1977, pp. 8485. MR 0429721 (55:2732)
 [5]
 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)
 [6]
 H. C. WILLIAMS & J. S. JUDD, "Some algorithms for prime testing using generalized Lehmer functions," Math. Comp., v. 30, 1976, pp. 867886. MR 0414473 (54:2574)
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/S00255718197804766250
PII:
S 00255718(1978)04766250
Article copyright:
© Copyright 1978 American Mathematical Society
