Asymptotically fast factorization of integers

Author:
John D. Dixon

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

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 for some constant . Asymptotically, this algorithm is much faster than any previously analyzed algorithm for factoring integers; earlier algorithms have all required operations where .

**[1]**N. G. de Bruijn,*On the number of positive integers ≤𝑥 and free prime factors >𝑦. II*, Nederl. Akad. Wetensch. Proc. Ser. A 69=Indag. Math.**28**(1966), 239–247. MR**0205945****[2]**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**0484750**, https://doi.org/10.1002/cpa.3160310407**[3]**William Feller,*An Introduction to Probability Theory and Its Applications. Vol. I*, John Wiley & Sons, Inc., New York, N.Y., 1950. MR**0038583****[4]**H. Halberstam,*On integers all of whose prime factors are small*, Proc. London Math. Soc. (3)**21**(1970), 102–107. MR**0269614**, https://doi.org/10.1112/plms/s3-21.1.102**[5]**Donald E. Knuth,*The art of computer programming. Vol. 2*, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms; Addison-Wesley Series in Computer Science and Information Processing. MR**633878****[6]**R. Sherman Lehman,*Factoring large integers*, Math. Comp.**28**(1974), 637–646. MR**0340163**, https://doi.org/10.1090/S0025-5718-1974-0340163-2**[7]**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**, https://doi.org/10.1016/S0022-0000(76)80043-8

Gary L. Miller,*Riemann’s hypothesis and tests for primality*, Seventh Annual ACM Symposium on Theory of Computing (Albuquerque, N.M., 1975), Assoc. Comput. Mach., New York, 1975, pp. 234–239. MR**0480296****[8]**J. M. Pollard,*Theorems on factorization and primality testing*, Proc. Cambridge Philos. Soc.**76**(1974), 521–528. MR**0354514****[9]**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****[10]**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**, https://doi.org/10.1145/359340.359342**[11]**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****[12]**R. Solovay and V. Strassen,*A fast Monte-Carlo test for primality*, SIAM J. Comput.**6**(1977), no. 1, 84–85. MR**0429721**, https://doi.org/10.1137/0206006**[13]**I. M. Vinogradov,*Elements of number theory*, Dover Publications, Inc., New York, 1954. Translated by S. Kravetz. MR**0062138**

Retrieve articles in *Mathematics of Computation*
with MSC:
10A30,
10A25

Retrieve articles in all journals with MSC: 10A30, 10A25

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1981-0595059-1

Article copyright:
© Copyright 1981
American Mathematical Society