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
Additional Information
- © Copyright 1981 American Mathematical Society
- Journal: Math. Comp. 36 (1981), 255-260
- MSC: Primary 10A30; Secondary 10A25
- DOI: https://doi.org/10.1090/S0025-5718-1981-0595059-1
- MathSciNet review: 595059