An $O(n^{1/10.89})$ primality testing algorithm
HTML articles powered by AMS MathViewer
- by Leonard Adleman and Frank Thomson Leighton PDF
- Math. Comp. 36 (1981), 261-266 Request permission
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
- D. A. Burgess, The distribution of quadratic residues and non-residues, Mathematika 4 (1957), 106–112. MR 93504, DOI 10.1112/S0025579300001157
- D. A. Burgess, On character sums and primitive roots, Proc. London Math. Soc. (3) 12 (1962), 179–192. MR 132732, DOI 10.1112/plms/s3-12.1.179
- D. A. Burgess, On character sums and $L$-series, Proc. London Math. Soc. (3) 12 (1962), 193–206. MR 132733, DOI 10.1112/plms/s3-12.1.193
- Gary L. Miller, Riemann’s hypothesis and tests for primality, J. Comput. System Sci. 13 (1976), no. 3, 300–317. MR 480295, DOI 10.1016/S0022-0000(76)80043-8
- Karl K. Norton, Numbers with small prime factors, and the least $k$th power non-residue, Memoirs of the American Mathematical Society, No. 106, American Mathematical Society, Providence, R.I., 1971. MR 0286739
- J. M. Pollard, An algorithm for testing the primality of any integer, Bull. London Math. Soc. 3 (1971), 337–340. MR 294245, DOI 10.1112/blms/3.3.337
- J. M. Pollard, Theorems on factorization and primality testing, Proc. Cambridge Philos. Soc. 76 (1974), 521–528. MR 354514, DOI 10.1017/s0305004100049252
- 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
- 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
Additional Information
- © Copyright 1981 American Mathematical Society
- Journal: Math. Comp. 36 (1981), 261-266
- MSC: Primary 10A25; Secondary 10-04, 68C25
- DOI: https://doi.org/10.1090/S0025-5718-1981-0595060-8
- MathSciNet review: 595060