Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Primality testing and Jacobi sums


Authors: H. Cohen and H. W. Lenstra
Journal: Math. Comp. 42 (1984), 297-330
MSC: Primary 11Y11; Secondary 11A51
DOI: https://doi.org/10.1090/S0025-5718-1984-0726006-X
MathSciNet review: 726006
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We present a theoretically and algorithmically simplified version of a primality testing algorithm that was recently invented by Adleman and Rumely. The new algorithm performs well in practice. It is the first primality test in existence that can routinely handle numbers of hundreds of decimal digits.


References [Enhancements On Off] (What's this?)

  • [1] L. M. Adleman, C. Pomerance & R. S. Rumely, "On distinguishing prime numbers from composite numbers," Ann. of Math., v. 117, 1983, pp. 173-206. MR 683806 (84e:10008)
  • [2] J. Brillhart, D. H. Lehmer & J. L. Selfridge, "New primality criteria and factorizations of $ {2^m} \pm 1$," Math. Comp., v. 29, 1975, pp. 620-647. MR 0384673 (52:5546)
  • [3] D. A. Burgess, "On the quadratic character of a polynomial," J. London Math. Soc., v. 42, 1967, pp. 73-80. MR 0205940 (34:5765)
  • [4] G. H. Hardy & E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford Univ. Press, Oxford, 1979. MR 568909 (81i:10002)
  • [5] H. Hasse, Vorlesungen über Zahlentheorie, 2nd ed., Springer-Verlag, Berlin, 1964. MR 0153659 (27:3621)
  • [6] H. Hasse, Zahlentheorie, 3rd ed., Akademie-Verlag, Berlin, 1969; English transl.: Number Theory, Springer-Verlag, Berlin, 1980. MR 0253972 (40:7185)
  • [7] J. R. Joly, "Equations et variétés algébriques sur un corps fini," Enseign. Math., v. 19, 1973, pp. 1-117. MR 0327723 (48:6065)
  • [8] D. E. Knuth, The Art of Computer Programming, Vol. 2, Seminumerical Algorithms, 2nd ed., Addison-Wesley, Reading, Mass., 1981. MR 633878 (83i:68003)
  • [9] J. C. Lagarias, H. L. Montgomery & A. M. Odlyzko, "A bound for the least prime ideal in the Chebotarev density theorem," Invent. Math., v. 54, 1979, pp. 271-296. MR 553223 (81b:12013)
  • [10] S. Lang, Algebra, Addison-Wesley, Reading, Mass., 1965. MR 0197234 (33:5416)
  • [11] S. Lang, Algebraic Number Theory, Addison-Wesley, Reading, Mass., 1970. MR 0282947 (44:181)
  • [12] S. Lang, Cyclotomic Fields, Springer-Verlag, New York, 1978. MR 0485768 (58:5578)
  • [13] D. H. Lehmer, "On Fermat's quotient, base two," Math. Comp., v. 36, 1981, pp. 289-290. MR 595064 (82e:10004)
  • [14] D. H. Lehmer, "Strong Carmichael numbers," J. Austral. Math. Soc. Ser. A, v. 21, 1976, pp. 508-510. MR 0417032 (54:5093)
  • [15] H. W. Lenstra, Jr., "Divisors in residue classes," Math. Comp., v. 42, 1984, pp. 331-340. MR 726007 (85b:11118)
  • [16] H. W. Lenstra, Jr., Primality Testing Algorithms (after Adleman, Rumely and Williams), Sém. Bourbaki, Vol. 33, 1980/1981, Exposé 576, pp. 243-257 in: Lecture Notes in Math., Vol. 901, Springer-Verlag, Berlin, 1981. MR 647500 (83g:10002)
  • [17] H. W. Lenstra, Jr., "Primality testing with Artin symbols," pp. 341-347 in: N. Koblitz (ed.), Number Theory Related to Fermat's Last Theorem, Progress in Mathematics, Vol. 26, Birkhäuser, Boston, 1982. MR 685308 (84h:10010)
  • [18] S. Martello & P. Toth, "The 0-1 knapsack problem," Ch. 9, pp. 237-279 in: N. Christofides, A. Mingozzi, P. Toth and C. Sandi (eds.), Combinatorial Optimization, Wiley, New York, 1979. MR 557004 (82a:90099)
  • [19] G. L. Miller, "Riemann's hypothesis and tests for primality," J. Comput. System Sci., v. 13, 1976., pp. 300-317. MR 0480295 (58:470a)
  • [20] K. Prachar, "Über die Anzahl der Teiler einer natürlichen Zahl, welche die Form $ p - 1$ haben," Monatsh. Math., v. 59, 1955, pp. 91-97. MR 0068569 (16:904h)
  • [21] M. O. Rabin, "Probabilistic algorithms for testing primality," J. Number Theory, v. 12, 1980, pp. 128-138. MR 566880 (81f:10003)
  • [22] J.-P. Serre, Cours d'Arithmetique, Presses Universitaires de France, Paris, 1970, English transl.: A Course in Arithmetic, Springer-Verlag, New York, 1973. MR 0255476 (41:138)
  • [23] R. Solovay & V. Strassen, "A fast Monte-Carlo test for primality," SIAM J. Comput., v. 6, 1977, pp. 84-85; erratum, ibid., v. 7, 1978, p. 118. MR 0429721 (55:2732)
  • [24] J. Vélu, "Tests for primality under the Riemann hypothesis," SIGACT News, v. 10, 1978, pp. 58-59.
  • [25] L. C. Washington, Introduction to Cyclotomic Fields, Springer-Verlag, New York, 1982. MR 718674 (85g:11001)
  • [26] H. C. Williams, "Primality testing on a computer," Ars Combin., v. 5, 1978, pp. 127-185. MR 504864 (80d:10002)

Similar Articles

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-1984-0726006-X
Keywords: Primality testing, Jacobi sum
Article copyright: © Copyright 1984 American Mathematical Society

American Mathematical Society