A performance analysis of a simple primetesting algorithm
Author:
M. C. Wunderlich
Journal:
Math. Comp. 40 (1983), 709714
MSC:
Primary 10A25; Secondary 1004
MathSciNet review:
689483
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: This paper gives an empirical performance analysis of a primeproving 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, and J.
L. Selfridge, New primality criteria and
factorizations of 2^{𝑚}±1, Math.
Comp. 29 (1975),
620–647. MR 0384673
(52 #5546), http://dx.doi.org/10.1090/S00255718197503846731
 [2]
Michael
A. Morrison and John
Brillhart, A method of factoring and the
factorization of 𝐹₇, Math.
Comp. 29 (1975),
183–205. Collection of articles dedicated to Derrick Henry Lehmer on
the occasion of his seventieth birthday. MR 0371800
(51 #8017), http://dx.doi.org/10.1090/S00255718197503718005
 [3]
Michael
O. Rabin, Probabilistic algorithm for testing primality, J.
Number Theory 12 (1980), no. 1, 128–138. MR 566880
(81f:10003), http://dx.doi.org/10.1016/0022314X(80)900840
 [4]
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
(51 #5461)
 [5]
R.
Solovay and V.
Strassen, A fast MonteCarlo test for primality, SIAM J.
Comput. 6 (1977), no. 1, 84–85. MR 0429721
(55 #2732)
 [6]
H.
C. Williams, Primality testing on a computer, Ars Combin.
5 (1978), 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. 272276.
 [1]
 John Brillhart, D. H. Lehmer & J. L. Selfridge, "New primality criteria and factorizations of ," Math. Comp., v. 29, 1975, pp. 620647. MR 0384673 (52:5546)
 [2]
 Michael A. Morrison & John Brillhart, "A method of factoring and the factoring of ," Math. Comp., v. 29, 1975, pp. 183205. MR 0371800 (51:8017)
 [3]
 Michael O. Rabin, "Probabilistic algorithm for testing primality." J. Number Theory, v. 12, 1980, pp. 128138. 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. 109120. MR 0369226 (51:5461)
 [5]
 R. Solovay & V. Strassen, "A fast MonteCarlo test for primality," SIAM J. Comput., v. 6, 1977, pp. 8485. MR 0429721 (55:2732)
 [6]
 H. C. Williams, "Primality testing on a computer," Ars Combin., v. 5, 1978, pp. 127185. 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. 272276.
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
10A25,
1004
Retrieve articles in all journals
with MSC:
10A25,
1004
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718198306894838
PII:
S 00255718(1983)06894838
Article copyright:
© Copyright 1983
American Mathematical Society
