Some observations on primality testing

Authors:
H. C. Williams and R. Holte

Journal:
Math. Comp. **32** (1978), 905-917

MSC:
Primary 10A25; Secondary 10-04

DOI:
https://doi.org/10.1090/S0025-5718-1978-0476625-0

MathSciNet review:
0476625

Full-text PDF

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 & J. L. SELFRIDGE, "New primality criteria and factorizations of ,"*Math. Comp.*, v. 29, 1975, pp. 620-647. MR**0384673 (52:5546)****[2]**GARY L. MILLER, "Riemann's hypothesis and tests for primality,"*J. Comput. System Sci.*, v. 13, 1976, pp. 300-317. MR**0480295 (58:470a)****[3]**NOEL B. SLATER, "Gaps and steps for the sequence ,"*Proc. Cambridge Philos. Soc.*, v. 63, 1967, pp. 1115-1123. MR**0217019 (36:114)****[4]**R. SOLOVAY & V. STRASSEN, "A fast Monte-Carlo test for primality,"*SIAM J. Comput.*, v. 6, 1977, pp. 84-85. 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. 157-172. 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. 867-886. MR**0414473 (54:2574)**

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-1978-0476625-0

Article copyright:
© Copyright 1978
American Mathematical Society