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

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**, 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**, 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**, 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**, 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**0429721****[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