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

MathSciNet review:
0476625

Full-text 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**, 10.1090/S0025-5718-1975-0384673-1**[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 ACM-SIGACT Symposium on the Theory of Computing (Albuquerque, N.M., 1975). MR**0480295****[3]**Noel B. Slater,*Gaps and steps for the sequence 𝑛𝜃𝑚𝑜𝑑1*, Proc. Cambridge Philos. Soc.**63**(1967), 1115–1123. MR**0217019****[4]**R. Solovay and V. Strassen,*A fast Monte-Carlo test for primality*, SIAM J. Comput.**6**(1977), no. 1, 84–85. MR**0429721****[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**, 10.1090/S0025-5718-1976-0396390-3**[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**, 10.1090/S0025-5718-1976-0414473-6

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