A performance analysis of a simple prime-testing algorithm

Wunderlich, M. C.

doi:10.1090/S0025-5718-1983-0689483-8

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 Free Access

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

John Brillhart, D. H. Lehmer, and J. L. Selfridge, New primality criteria and factorizations of $2^{m}\pm 1$, Math. Comp. 29 (1975), 620–647. MR 384673, DOI https://doi.org/10.1090/S0025-5718-1975-0384673-1
Michael A. Morrison and John Brillhart, A method of factoring and the factorization of $F_{7}$, Math. Comp. 29 (1975), 183–205. MR 371800, DOI https://doi.org/10.1090/S0025-5718-1975-0371800-5
Michael O. Rabin, Probabilistic algorithm for testing primality, J. Number Theory 12 (1980), no. 1, 128–138. MR 566880, DOI https://doi.org/10.1016/0022-314X%2880%2990084-0
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
R. Solovay and V. Strassen, A fast Monte-Carlo test for primality, SIAM J. Comput. 6 (1977), no. 1, 84–85. MR 429721, DOI https://doi.org/10.1137/0206006
H. C. Williams, Primality testing on a computer, Ars Combin. 5 (1978), 127–185. MR 504864

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.