An 𝑂(𝑛^{1/10.89}) primality testing algorithm

Adleman, Leonard; Leighton, Frank Thomson

doi:10.1090/S0025-5718-1981-0595060-8

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