Remote Access Journal of the American Mathematical Society
Green Open Access

Journal of the American Mathematical Society

ISSN 1088-6834(online) ISSN 0894-0347(print)



A rigorous time bound for factoring integers

Authors: H. W. Lenstra and Carl Pomerance
Journal: J. Amer. Math. Soc. 5 (1992), 483-516
MSC: Primary 11Y05; Secondary 11E41, 11Y35, 11Y40
MathSciNet review: 1137100
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper a probabilistic algorithm is exhibited that factors any positive integer $ n$ into prime factors in expected time at most $ {L_n}[\tfrac{1}{2},1 + o(1)]$ for $ n \to \infty $, where $ {L_x}[a,b] = {\text{exp}}(b{(\log x)^a}{({\text{log}}\log x)^{1 - a}})$. Many practical factoring algorithms, including the quadratic sieve and the elliptic curve method, are conjectured to have an expected running time that satisfies the same bound, but this is the first algorithm for which the bound can be rigorously proved. Nevertheless, this does not close the gap between rigorously established time bounds and merely conjectural ones for factoring algorithms. This is due to the advent of a new factoring algorithm, the number field sieve, which is conjectured to factor any positive integer $ n$ in time $ {L_n}[\tfrac{1}{3},O(1)]$.

The algorithm analyzed in this paper is a variant of the class group relations method, which makes use of class groups of binary quadratic forms of negative discriminant. This algorithm was first suggested by Seysen, and later improved by A. K. Lenstra, who showed that the algorithm runs in expected time at most $ {L_n}[\tfrac{1}{2},1 + o(1)]$ if one assumes the generalized Riemann hypothesis. The main device for removing the use of the generalized Riemann hypothesis from the proof is the use of multipliers. In addition a character sum estimate for algebraic number fields is used, with an explicit dependence on possible exceptional zeros of the corresponding $ L$-functions.

Another factoring algorithm using class groups that has been proposed is the random class groups method. It is shown that there is a fairly large set of numbers that this algorithm cannot be expected to factor as efficiently as had previously been thought.

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

  • [1] L. M. Adleman, C. Pomerance, and R. S. Rumely, On distinguishing prime numbers from composite numbers, Ann. of Math. (2) 117 (1983), 173-206. MR 683806 (84e:10008)
  • [2] Z. I. Borevič and I. R. Šafarevič, Teorija čisel, Izdat. ``Nauka'', Moscow, 1964; English transl., Number theory, Academic Press, New York, 1966.
  • [3] R. P. Brent, Fast multiple-precision evaluation of elementary functions, J. Assoc. Comput. Mach. 23 (1976), 242-251. MR 0395314 (52:16111)
  • [4] J. P. Buhler, H. W. Lenstra, Jr., and C. Pomerance, Factoring integers with the number field sieve, in preparation.
  • [5] E. R. Canfield, P. Erdős, and C. Pomerance, On a problem of Oppenheim concerning ``factorisatio numerorum,'' J. Number Theory 17 (1983), 1-28. MR 712964 (85j:11012)
  • [6] D. Coppersmith, Modifications to the number field sieve, IBM Research Report RC 16264 (#72241), Yorktown Heights, 1990. MR 1233462 (94h:11111)
  • [7] D. A. Cox, Primes of the form $ {x^2} + n{y^2}$, Wiley, New York, 1989. MR 1028322 (90m:11016)
  • [8] H. Davenport, Multiplicative number theory, 2nd ed., Springer-Verlag, New York, 1980. MR 606931 (82m:10001)
  • [9] P. G. Lejeune Dirichlet and R. Dedekind, Vorlesungen über Zahlentheorie, 4th ed., Vieweg, Braunschweig, 1893; reprint, Chelsea, New York, 1968.
  • [10] J. D. Dixon, Asymptotically fast factorization of integers, Math. Comp. 36 (1981), 255-260. MR 595059 (82a:10010)
  • [11] W. J. Ellison, Les nombres premiers, Hermann, Paris, 1975. MR 0417077 (54:5138)
  • [12] J. B. Friedlander and J. C. Lagarias, On the distribution in short intervals of integers having no large prime factor, J. Number Theory 25 (1987), 249-273. MR 880461 (88d:11084)
  • [13] J. L. Hafner and K. S. McCurley, A rigorous subexponential algorithm for computation of class groups, J. Amer. Math. Soc. 2 (1989), 837-850. MR 1002631 (91f:11090)
  • [14] D. S. Johnson, The NP-completeness column: an ongoing guide, J. Algorithms 5 (1984), 433-447. MR 756168 (86a:68038b)
  • [15] J. C. Lagarias, Worst-case complexity bounds for algorithms in the theory of integral quadratic forms, J. Algorithms 1 (1980), 142-186. MR 604862 (83e:90112)
  • [16] J. C. Lagarias, H. L. Montgomery, and A. M. Odlyzko, A bound for the least prime ideal in the Chebotarev density theorem, Invent. Math. 54 (1979), 271-296. MR 553223 (81b:12013)
  • [17] J. C. Lagarias and A. M. Odlyzko, Effective versions of the Chebotarev density theorem, A. Fröhlich (ed.), Algebraic Number Fields: $ L$-functions and Galois Properties, Academic Press, London, 1977, pp. 409-464. MR 0447191 (56:5506)
  • [18] S. Lang, Algebraic number theory, Addison-Wesley, Reading, Mass., 1970. MR 0282947 (44:181)
  • [19] A. K. Lenstra, Factorization of polynomials, in [27], pp. 169-198. MR 700263 (85a:12002)
  • [20] -, Fast and rigorous factorization under the generalized Riemann hypothesis, Nederl. Akad. Wetensch. Proc. Ser. A 91 (Indag. Math. 50) (1988), 443-454. MR 976527 (90a:11152)
  • [21] A. K. Lenstra and H. W. Lenstra, Jr., Algorithms in number theory, J. van Leeuwen (ed.), Handbook of Theoretical Computer Science, Volume A, Algorithms and Complexity, Elsevier, Amsterdam, 1990, Chapter 12, pp. 673-715. MR 1127178
  • [22] A. K. Lenstra, H. W. Lenstra, Jr., M. S. Manasse, and J. M. Pollard, The factorization of the ninth Fermat number, in preparation.
  • [23] -, The number field sieve, in preparation. Extended abstract: Proc. 22nd Annual ACM Symp. on Theory of Computing (STOC), Baltimore, May 14-16, 1990, pp. 564-572.
  • [24] H. W. Lenstra, Jr., Factoring integers with elliptic curves, Ann. of Math. (2) 126 (1987), 649-673. MR 916721 (89g:11125)
  • [25] -, On the calculation of regulators and class numbers of quadratic fields, J. Armitage (ed.), Journées Arithmétiques 1980, London Math. Soc. Lecture Note Ser., no. 56, Cambridge University Press, Cambridge, 1982, pp. 123-150. MR 697260 (86g:11080)
  • [26] -, Primality testing algorithms, Séminaire Bourbaki 33, exp. no. 576, Lecture Notes in Math., vol. 901, Springer-Verlag, Heidelberg, 1981, pp. 243-257.
  • [27] H. W. Lenstra, Jr. and R. Tijdeman (eds), Computational methods in number theory, Mathematical Centre Tracts 154/155, Mathematisch Centrum, Amsterdam, 1982. MR 700254 (84c:10002)
  • [28] C. Pomerance, Fast, rigorous factorization and discrete logarithm algorithms, D. S. Johnson, T. Nishizeki, A. Nozaki, H. S. Wilf (eds), Discrete Algorithms and Complexity, Academic Press, Orlando, 1987, pp. 119-143. MR 910929 (88m:11109)
  • [29] C. P. Schnorr and H. W. Lenstra, Jr., A Monte Carlo factoring algorithm with linear storage, Math. Comp. 43 (1984), 289-311. MR 744939 (85d:11106)
  • [30] R. J. Schoof, Quadratic fields and factorization, in [27], pp. 235-286. MR 702519 (85g:11118b)
  • [31] I. Schur, Einige Bemerkungen zu der vorstehenden Arbeit des Herrn G. Pólya: Über die Verteilung der quadratischen Reste und Nichtreste, Nachr. Kön. Ges. Wiss. Göttingen, Math.- phys. Kl. (1918), 30-36; Gesammelte Abhandlungen, vol. II, Springer, Berlin, 1973, pp. 239-245.
  • [32] M. Seysen, A probabilistic factorization algorithm with quadratic forms of negative discriminant, Math. Comp. 48 (1987), 757-780. MR 878705 (88d:11129)
  • [33] B. Vallée, Generation of elements with small modular squares and provably fast integer factoring algorithms, Math. Comp. 56 (1991), 823-849. MR 1068808 (91i:11183)
  • [34] D. Wiedemann, Solving sparse linear equations over finite fields, IEEE Trans. Inform. Theory 32 (1986), 54-62. MR 831560 (87g:11166)

Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC: 11Y05, 11E41, 11Y35, 11Y40

Retrieve articles in all journals with MSC: 11Y05, 11E41, 11Y35, 11Y40

Additional Information

Keywords: Factorization algorithm, class groups, binary quadratic forms, smooth numbers
Article copyright: © Copyright 1992 American Mathematical Society

American Mathematical Society