Implementation of a new primality test

Cohen, H.; Lenstra, A. K.

doi:10.1090/S0025-5718-1987-0866102-2

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