Implementation of a new primality test
Authors:
H. Cohen and A. K. Lenstra
Journal:
Math. Comp. 48 (1987), 103-121, S1
MSC:
Primary 11Y11; Secondary 11A51
DOI:
https://doi.org/10.1090/S0025-5718-1987-0866102-2
MathSciNet review:
866102
Full-text PDF Free Access
Abstract | References | Similar Articles | Additional Information
Abstract: An implementation of the Cohen-Lenstra version of the Adleman-Pomerance-Rumely primality test is presented. Primality of prime numbers of up to 213 decimal digits can now routinely be proved within approximately ten minutes.
- [1] Leonard M. Adleman, Carl Pomerance, and Robert S. Rumely, On distinguishing prime numbers from composite numbers, Ann. of Math. (2) 117 (1983), no. 1, 173–206. MR 683806, https://doi.org/10.2307/2006975
- [2] H. Cohen and H. W. Lenstra Jr., Primality testing and Jacobi sums, Math. Comp. 42 (1984), no. 165, 297–330. MR 726006, https://doi.org/10.1090/S0025-5718-1984-0726006-X
- [3] John Brillhart, D. H. Lehmer, J. L. Selfridge, Bryant Tuckerman, and S. S. Wagstaff Jr., Factorizations of 𝑏ⁿ±1, Contemporary Mathematics, vol. 22, American Mathematical Society, Providence, R.I., 1983. 𝑏=2,3,5,6,7,10,11,12 up to high powers. MR 715603
- [4] Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms; Addison-Wesley Series in Computer Science and Information Processing. MR 633878
- [5] H. W. Lenstra Jr., Primality testing algorithms (after Adleman, Rumely and Williams), Bourbaki Seminar, Vol. 1980/81, Lecture Notes in Math., vol. 901, Springer, Berlin-New York, 1981, pp. 243–257. MR 647500
- [6] H. W. Lenstra Jr., Divisors in residue classes, Math. Comp. 42 (1984), no. 165, 331–340. MR 726007, https://doi.org/10.1090/S0025-5718-1984-0726007-1
- [7] H. W. Lenstra Jr. and R. Tijdeman (eds.), Computational methods in number theory. Part I, Mathematical Centre Tracts, vol. 154, Mathematisch Centrum, Amsterdam, 1982. MR 700254
- [8] Michael O. Rabin, Probabilistic algorithm for testing primality, J. Number Theory 12 (1980), no. 1, 128–138. MR 566880, https://doi.org/10.1016/0022-314X(80)90084-0
- [9] R. Solovay and V. Strassen, A fast Monte-Carlo test for primality, SIAM J. Comput. 6 (1977), no. 1, 84–85. MR 429721, https://doi.org/10.1137/0206006
- [10] H. C. Williams, Primality testing on a computer, Ars Combin. 5 (1978), 127–185. MR 504864
Retrieve articles in Mathematics of Computation with MSC: 11Y11, 11A51
Retrieve articles in all journals with MSC: 11Y11, 11A51
Additional Information
DOI:
https://doi.org/10.1090/S0025-5718-1987-0866102-2
Keywords:
Primality testing
Article copyright:
© Copyright 1987
American Mathematical Society