A performance analysis of a simple prime-testing algorithm

Author:
M. C. Wunderlich

Journal:
Math. Comp. **40** (1983), 709-714

MSC:
Primary 10A25; Secondary 10-04

DOI:
https://doi.org/10.1090/S0025-5718-1983-0689483-8

MathSciNet review:
689483

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: This paper gives an empirical performance analysis of a prime-proving program designed and implemented by the author and J. L. Selfridge in 1974. The algorithm has been commonly referred to as the "down algorithm" because of its recursive characteristics. It is shown, among other things, that of the 2270 primes tested, 94

**[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]**Michael A. Morrison & John Brillhart, "A method of factoring and the factoring of ,"*Math. Comp.*, v. 29, 1975, pp. 183-205. MR**0371800 (51:8017)****[3]**Michael O. Rabin, "Probabilistic algorithm for testing primality."*J. Number Theory*, v. 12, 1980, pp. 128-138. MR**566880 (81f:10003)****[4]**J. L. Selfridge & M. C. Wunderlich,*An Efficient Algorithm for Testing Large Numbers for Primality*, Congressus Numeratium XII, Proc. 4th Manitoba Conf. on Numerical Math. (Winnipeg, 1973), Utilitas Math., Winnipeg, 1974, pp. 109-120. MR**0369226 (51:5461)****[5]**R. Solovay & V. Strassen, "A fast Monte-Carlo test for primality,"*SIAM J. Comput.*, v. 6, 1977, pp. 84-85. MR**0429721 (55:2732)****[6]**H. C. Williams, "Primality testing on a computer,"*Ars Combin.*, v. 5, 1978, pp. 127-185. MR**504864 (80d:10002)****[7]**Marvin 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.

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-1983-0689483-8

Article copyright:
© Copyright 1983
American Mathematical Society