Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



A Monte Carlo factoring algorithm with linear storage

Authors: C.-P. Schnorr and H. W. Lenstra
Journal: Math. Comp. 43 (1984), 289-311
MSC: Primary 11Y05; Secondary 68Q25
MathSciNet review: 744939
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We present an algorithm which will factor an integer n quite efficiently if the class number $ h( - n)$ is free of large prime divisors. The running time $ T(n)$ (number of compositions in the class group) satisfies $ \operatorname{prob}[T(m) \leqslant {n^{1/2r}}] \gtrsim {(r - 2)^{ - (r - 2)}}$ for random $ m \in [n/2,n]$ and $ r \geqslant 2$. So far it is unpredictable which numbers will be factored fast. Running the algorithm on all discriminants - ns with $ s \leqslant {r^r}$ and $ r = \sqrt {\ln n/\ln \ln n} $, every composite integer n will be factored in $ o(\exp \sqrt {\ln n\ln \ln n} )$ bit operations. The method requires an amount of storage space which is proportional to the length of the input n. In our analysis we assume a lower bound on the frequency of class numbers $ h( - m)$, $ m \leqslant n$, which are free of large prime divisors.

References [Enhancements On Off] (What's this?)

  • [1] R. P. Brent, "An improved Monte Carlo factorization algorithm," BIT, v. 20, 1980, pp. 176-184. MR 583032 (82a:10007)
  • [2] J. W. S. Cassels, Rational Quadratic Forms, Academic Press, London, New York, 1978. MR 522835 (80m:10019)
  • [3] H. Cohen & H. W. Lenstra, Jr., Divisibility by Small Primes of Class Numbers, Personal communication, 1982.
  • [4] J. D. Dixon, "Asymptotically fast factorization of integers," Math. Comp., v. 36, 1981, pp. 255-260. MR 595059 (82a:10010)
  • [5] C. F. Gauss, Disquisitiones Arithmeticae, Leipzig, 1801: English transl. by A. A. Clarke, Yale University Press, New Haven and London, 1966. MR 0197380 (33:5545)
  • [6] G. H. Hardy & E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford Univ. Press, Oxford, 1979. MR 568909 (81i:10002)
  • [7] D. E. Knuth, The Art of Computer Programming, Vol. 2, Seminumerical Algorithms, 2nd ed., Addison-Wesley, Reading, Mass., 1981. MR 633878 (83i:68003)
  • [8] P. G. Lejeune Dirichlet & R. Dedekind, Vorlesungen über Zahlentheorie, Braunschweig, 1893; reprint, New York, 1968.
  • [9] H. W. Lenstra, Jr., On the Calculation of Regulators and Class Numbers of Quadratic Fields, Journées Arithmétiques 1980 (J. V. Armitage, Ed.), Cambridge Univ. Press, Oxford, 1982, pp. 123-150. MR 697260 (86g:11080)
  • [10] G. B. Mathews, Theory of numbers, 1892; Reprint, Chelsea, New York, 1962. MR 0126402 (23:A3698)
  • [11] L. Monier, Algorithmes de Factorisation d'Entiers, Thèse d'informatique, Université Paris Sud, 1980.
  • [12] M. A. Morrison & J. Brillhart, "A method of factorization and the factorization of $ {F_7}$," Math. Comp., v. 29, 1975, pp. 183-205. MR 0371800 (51:8017)
  • [13] J. M. Pollard, "A Monte Carlo method for factorization," BIT, v. 15, 1975, pp. 331-334. MR 0392798 (52:13611)
  • [14] C. Pomerance, "Analysis and comparison of some integer factoring algorithms," Computational Methods in Number Theory (R. Tijdemen and H. Lenstra, Eds.), Mathematical Centrum, Amsterdam, 1981. MR 700260 (84i:10005)
  • [15] R. L. Rivest, A. Shamir & L. Adleman, "A method for obtaining digital signatures and public key cryptosystems," Comm. ACM, v. 21, 1978, pp. 120-126. MR 700103 (83m:94003)
  • [16] J. Sattler & C. P. Schnorr, "Ein Effizienzvergleich der Faktorisierungsverfahren von Morrison-Brillhart und Schroeppel," Computing, v. 30, 1983, pp. 91-110. MR 698122 (84g:10004)
  • [17] D. Shanks, Class Number, A Theory of Factorization, and Genera, Proc. Sympos. Pure Math., vol. 20, Amer. Math. Soc., Providence, R. I., 1971, pp. 415-440. MR 0316385 (47:4932)
  • [18] J. Sattler & C. P. Schnorr, Generating Random Walks in Groups, Preprint, Universität Frankfurt, 1983; submitted for publication. MR 915225 (89a:68108)
  • [19] C. P. Schnorr, "Refined analysis and improvements on some factoring algorithms," J. Algorithms, v. 3, 1982, pp. 101-127. MR 657269 (83g:10003)
  • [20] C. P. Schnorr & M. Seysen, An Improved Composition Algorithm, Preprint, Universität Frankfurt, 1982; submitted for publication.
  • [21] C. L. Siegel, "Über die Klassenzahl quadratischer Zahlkörper," Acta Arith., v. 1, 1936, pp. 83-86.
  • [22] S. S. Wagstaff & M. C. Wunderlich, A Comparison of Two Factorization Methods, Unpublished manuscript.
  • [23] H. G. Zimmer, Computational Problems, Methods, and Results in Algebraic Number Theory, Lecture Notes in Math., Vol. 262, Springer, Berlin and New York, 1972. MR 0323751 (48:2107)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11Y05, 68Q25

Retrieve articles in all journals with MSC: 11Y05, 68Q25

Additional Information

Article copyright: © Copyright 1984 American Mathematical Society

American Mathematical Society