Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

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 $ 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 [Enhancements On Off] (What's this?)

  • [1] N. G. de Brultn, "On the number of positive integers $ \leqslant x$ and free of prime factors $ > y$. 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)

Similar Articles

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

American Mathematical Society