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
HTML articles powered by AMS MathViewer

by H. Cohen and A. K. Lenstra PDF

Math. Comp. 48 (1987), 103-121 Request permission

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.

References

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, DOI 10.2307/2006975
H. Cohen and H. W. Lenstra Jr., Primality testing and Jacobi sums, Math. Comp. 42 (1984), no. 165, 297–330. MR 726006, DOI 10.1090/S0025-5718-1984-0726006-X
John Brillhart, D. H. Lehmer, J. L. Selfridge, Bryant Tuckerman, and S. S. Wagstaff Jr., Factorizations of $b^{n}\pm 1$, Contemporary Mathematics, vol. 22, American Mathematical Society, Providence, R.I., 1983. $b=2,\,3,\,5,\,6,\,7,\,10,\,11,\,12$ up to high powers. MR 715603
Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms. MR 633878
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
H. W. Lenstra Jr., Divisors in residue classes, Math. Comp. 42 (1984), no. 165, 331–340. MR 726007, DOI 10.1090/S0025-5718-1984-0726007-1
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
Michael O. Rabin, Probabilistic algorithm for testing primality, J. Number Theory 12 (1980), no. 1, 128–138. MR 566880, DOI 10.1016/0022-314X(80)90084-0
R. Solovay and V. Strassen, A fast Monte-Carlo test for primality, SIAM J. Comput. 6 (1977), no. 1, 84–85. MR 429721, DOI 10.1137/0206006
H. C. Williams, Primality testing on a computer, Ars Combin. 5 (1978), 127–185. MR 504864