Primality testing algorithms

H. W., Jr. Lenstra

Séminaire Bourbaki (1980-1981)

  • Volume: 23, page 243-257
  • ISSN: 0303-1179

How to cite


Lenstra, H. W., Jr.. "Primality testing algorithms." Séminaire Bourbaki 23 (1980-1981): 243-257. <>.

author = {Lenstra, H. W., Jr.},
journal = {Séminaire Bourbaki},
keywords = {probabilistic criteria; primality testing; power reciprocity; polynomial time algorithm; strong pseudoprime},
language = {eng},
pages = {243-257},
publisher = {Springer-Verlag},
title = {Primality testing algorithms},
url = {},
volume = {23},
year = {1980-1981},

AU - Lenstra, H. W., Jr.
TI - Primality testing algorithms
JO - Séminaire Bourbaki
PY - 1980-1981
PB - Springer-Verlag
VL - 23
SP - 243
EP - 257
LA - eng
KW - probabilistic criteria; primality testing; power reciprocity; polynomial time algorithm; strong pseudoprime
UR -
ER -


  1. 1. L.M. Adleman, On distinguishing prime numbers from composite numbers (abstract), Proc. 21st Annual IEEE Symposium on Foundations of Computer Science (1980), 387-406. 
  2. 2. L.M. Adleman, C. Pomerance, R.S. Rumely, On distinguishing prime numbers from composite numbers, preprint. Zbl0526.10004MR683806
  3. 3. S.U. Chase, D.K. Harrison, A. Rosenberg, Galois theory and Galois cohomology of commutative rings, Memoirs Amer. Math. Soc.52 (1965), 15-33. Zbl0143.05902MR195922
  4. 4. F. Demeyer, E. Ingraham, Separable algebras over commutative rings, Lecture Notes in Mathematics181, Springer, Berlin1971. Zbl0215.36602MR280479
  5. 5. R.K. Guy, How to factor a number, Proc. Fifth Manitoba Conf. Numer. Math., Utilitas, Winnipeg (1975), 49-89. Zbl0338.10001MR404120
  6. 6. D.E. Knuth, The art of computer programming, vol. 2, Seminumerical algorithms, second edition, Addison-Wesley, Reading1981. Zbl0191.18001MR633878
  7. 7. S. Lang, Cyclotomic fields, Springer, Berlin1978. Zbl0395.12005MR485768
  8. 8. H.W. Lenstra, Jr., Euclid's algorithm in cyclotomic fields, J. London Math. Soc. (2) 10 (1975), 457-465. Zbl0313.12001MR387257
  9. 9. J.M. Pollard, Theorems on factorization and primality testing, Proc. Cambridge Philos. Soc.76 (1974), 521-528. Zbl0294.10005MR354514
  10. 10. K. Prachar, Über die Anzahl der Teiler einer natürlichen Zahl, welche die Form p - 1 haben, Monatsh. Math.59 (1955), 91-97. Zbl0064.04107MR68569
  11. 11. C.P. Schnorr, Refined analysis and improvements on some factoring algorithms, to appear in: Automata, Languages and Programming, Eighth Colloquium, Haifa1981, Lecture Notes in Computer Science, to appear. Zbl0469.68043MR635126
  12. 12. R. Solovay, V. Strassen, A fast Monte-Carlo test for primality, SIAM J. Comput.6 (1977), 84-85; erratum, 7 (1978), 118. Zbl0373.10002MR429721
  13. 13. H.C. Williams, Primality testing on a computer, Ars Combin.5 (1978), 127-185. Zbl0406.10008MR504864

NotesEmbed ?


You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.


Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.