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.
Retrieve articles in Mathematics of Computation with MSC: 10A25, 10-04
Retrieve articles in all journals with MSC: 10A25, 10-04
Additional Information
Article copyright:
© Copyright 1983
American Mathematical Society