Asymptotically fast factorization of integers

Dixon, John D.

doi:10.1090/S0025-5718-1981-0595059-1

Asymptotically fast factorization of integers
HTML articles powered by AMS MathViewer

by John D. Dixon PDF

Math. Comp. 36 (1981), 255-260 Request permission

Abstract:

The paper describes a "probabilistic algorithm" for finding a factor of any large composite integer n (the required input is the integer n together with an auxiliary sequence of random numbers). It is proved that the expected number of operations which will be required is $O(\exp \{ \beta {(\ln n\ln \ln n)^{1/2}}\} )$ for some constant $\beta > 0$. Asymptotically, this algorithm is much faster than any previously analyzed algorithm for factoring integers; earlier algorithms have all required $O({n^\alpha })$ operations where $\alpha > 1/5$.

References

N. G. de Bruijn, On the number of positive integers $\leq x$ and free prime factors $>y$. II, Nederl. Akad. Wetensch. Proc. Ser. A 69=Indag. Math. 28 (1966), 239–247. MR 0205945
Gregory J. Chaitin and Jacob T. Schwartz, A note on Monte Carlo primality tests and algorithmic information theory, Comm. Pure Appl. Math. 31 (1978), no. 4, 521–527. MR 484750, DOI 10.1002/cpa.3160310407
William Feller, An Introduction to Probability Theory and Its Applications. Vol. I, John Wiley & Sons, Inc., New York, N.Y., 1950. MR 0038583
H. Halberstam, On integers all of whose prime factors are small, Proc. London Math. Soc. (3) 21 (1970), 102–107. MR 269614, DOI 10.1112/plms/s3-21.1.102
Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms. MR 633878
R. Sherman Lehman, Factoring large integers, Math. Comp. 28 (1974), 637–646. MR 340163, DOI 10.1090/S0025-5718-1974-0340163-2
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
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. L. Rivest, A. Shamir, and L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Comm. ACM 21 (1978), no. 2, 120–126. MR 700103, DOI 10.1145/359340.359342
Daniel Shanks, Class number, a theory of factorization, and genera, 1969 Number Theory Institute (Proc. Sympos. Pure Math., Vol. XX, State Univ. New York, Stony Brook, N.Y., 1969) Amer. Math. Soc., Providence, R.I., 1971, pp. 415–440. MR 0316385
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
I. M. Vinogradov, Elements of number theory, Dover Publications, Inc., New York, 1954. Translated by S. Kravetz. MR 0062138