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

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 Brultn, "On the number of positive integers and free of prime factors . II,"*Indag. Math.*, v. 28, 1966, pp 239-247. MR**0205945 (34:5770)****[2]**G. J. Chaitin & J. T. Schwartz, "A note on Monte Carlo primality tests and algorithmic information theory,"*Comm. Pure Appl. Math.*, v. 31, 1978, pp. 521-527. MR**0484750 (58:4629)****[3]**W. Feller,*Probability Theory and its Applications*. Vol. 1, Wiley, New York, 1950. MR**0038583 (12:424a)****[4]**H. Halberstam, "On integers all of whose prime factors are small,"*Proc. London Math. Soc.*, (3), v. 21, 1970, pp. 102-107. MR**0269614 (42:4509)****[5]**D. Knuth,*The Art of Computer Programming*. Vol. 2, Addison-Wesley, New York, 1971. MR**633878 (83i:68003)****[6]**R. S. Lehman, "Factoring large integers,"*Math. Comp.*, v. 28, 1974, pp. 637-646. MR**0340163 (49:4919)****[7]**G. L. Miller, "Riemann's hypothesis and tests for primality,"*J. Comput. System Sci.*, v. 13, 1976, pp. 300-317. MR**0480295 (58:470a)****[8]**J. M. Pollard, "Theorems on factorization and primality testing,"*Proc. Cambridge Philos. Soc.*, v. 76, 1974, pp. 521-528. MR**0354514 (50:6992)****[9]**M. O. Rabin, "Probabilistic algorithms,"*Algorithms and Complexity-New Directions and Recent Results*(J. F. Traub, Ed.), Academic Press, New York, 1976. MR**0464678 (57:4603)****[10]**R. L. Rivest, A. Shamir & L. Adleman, "A method for obtaining digital signatures and public-key cryptosystems,"*Comm. ACM*, v. 21, 1978, pp. 120-128. MR**700103 (83m:94003)****[11]**D. Shanks,*Class Number, a Theory of Factorization, and Genera*, Proc. Sympos. Pure Math., vol. 20, Amer. Math. Soc., Providence, R. I., 1970, pp. 415-440. MR**0316385 (47:4932)****[12]**R. Solovay & V. Strassen, "A fast Monte-Carlo test for primality,"*SIAM J. Comput.*, v. 6, 1977, pp. 84-85; Errata,*ibid.*, v. 7, 1978, p. 118. MR**0429721 (55:2732)****[13]**I. M. Vinogradov,*Elements of Number Theory*, 5th rev. ed., Dover, New York, 1954. MR**0062138 (15:933e)**

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