Mathematics of Computation

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

 

 

An $ O(n\sp{1/10.89})$ primality testing algorithm


Authors: Leonard Adleman and Frank Thomson Leighton
Journal: Math. Comp. 36 (1981), 261-266
MSC: Primary 10A25; Secondary 10-04, 68C25
MathSciNet review: 595060
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper, we describe an $ O({n^{1/10.89}})$ deterministic algorithm to decide primality. The algorithm incorporates several recent results in complexity theory.


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

  • [1] D. A. Burgess, The distribution of quadratic residues and non-residues, Mathematika 4 (1957), 106–112. MR 0093504
  • [2] D. A. Burgess, On character sums and primitive roots, Proc. London Math. Soc. (3) 12 (1962), 179–192. MR 0132732
  • [3] D. A. Burgess, On character sums and 𝐿-series, Proc. London Math. Soc. (3) 12 (1962), 193–206. MR 0132733
  • [4] Gary L. Miller, Riemann’s hypothesis and tests for primality, J. Comput. System Sci. 13 (1976), no. 3, 300–317. Working papers presented at the ACM-SIGACT Symposium on the Theory of Computing (Albuquerque, N.M., 1975). MR 0480295
  • [5] Karl K. Norton, Numbers with small prime factors, and the least 𝑘th power non-residue, Memoirs of the American Mathematical Society, No. 106, American Mathematical Society, Providence, R.I., 1971. MR 0286739
  • [6] J. M. Pollard, An algorithm for testing the primality of any integer, Bull. London Math. Soc. 3 (1971), 337–340. MR 0294245
  • [7] J. M. Pollard, Theorems on factorization and primality testing, Proc. Cambridge Philos. Soc. 76 (1974), 521–528. MR 0354514
  • [8] Michael O. Rabin, Probabilistic algorithms, Algorithms and complexity (Proc. Sympos., Carnegie-Mellon Univ., Pittsburgh, Pa., 1976) Academic Press, New York, 1976, pp. 21–39. MR 0464678
  • [9] R. Solovay and V. Strassen, A fast Monte-Carlo test for primality, SIAM J. Comput. 6 (1977), no. 1, 84–85. MR 0429721

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 10A25, 10-04, 68C25

Retrieve articles in all journals with MSC: 10A25, 10-04, 68C25


Additional Information

DOI: http://dx.doi.org/10.1090/S0025-5718-1981-0595060-8
Keywords: Algorithm, Carmichael number, composite, factor, prime, residue
Article copyright: © Copyright 1981 American Mathematical Society