A rigorous time bound for factoring integers
HTML articles powered by AMS MathViewer
- by H. W. Lenstra and Carl Pomerance
- J. Amer. Math. Soc. 5 (1992), 483-516
- DOI: https://doi.org/10.1090/S0894-0347-1992-1137100-0
- PDF | Request permission
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
- Leonard M. Adleman, Carl Pomerance, and Robert S. Rumely, On distinguishing prime numbers from composite numbers, Ann. of Math. (2) 117 (1983), no. 1, 173–206. MR 683806, DOI 10.2307/2006975 Z. I. Borevič and I. R. Šafarevič, Teorija čisel, Izdat. “Nauka”, Moscow, 1964; English transl., Number theory, Academic Press, New York, 1966.
- Richard P. Brent, Fast multiple-precision evaluation of elementary functions, J. Assoc. Comput. Mach. 23 (1976), no. 2, 242–251. MR 395314, DOI 10.1145/321941.321944 J. P. Buhler, H. W. Lenstra, Jr., and C. Pomerance, Factoring integers with the number field sieve, in preparation.
- E. R. Canfield, Paul Erdős, and Carl Pomerance, On a problem of Oppenheim concerning “factorisatio numerorum”, J. Number Theory 17 (1983), no. 1, 1–28. MR 712964, DOI 10.1016/0022-314X(83)90002-1
- Don Coppersmith, Modifications to the number field sieve, J. Cryptology 6 (1993), no. 3, 169–180. MR 1233462, DOI 10.1007/BF00198464
- David A. Cox, Primes of the form $x^2 + ny^2$, A Wiley-Interscience Publication, John Wiley & Sons, Inc., New York, 1989. Fermat, class field theory and complex multiplication. MR 1028322
- Harold Davenport, Multiplicative number theory, 2nd ed., Graduate Texts in Mathematics, vol. 74, Springer-Verlag, New York-Berlin, 1980. Revised by Hugh L. Montgomery. MR 606931 P. G. Lejeune Dirichlet and R. Dedekind, Vorlesungen über Zahlentheorie, 4th ed., Vieweg, Braunschweig, 1893; reprint, Chelsea, New York, 1968.
- John D. Dixon, Asymptotically fast factorization of integers, Math. Comp. 36 (1981), no. 153, 255–260. MR 595059, DOI 10.1090/S0025-5718-1981-0595059-1
- William John Ellison, Les nombres premiers, Publications de l’Institut de Mathématique de l’Université de Nancago, No. IX, Hermann, Paris, 1975 (French). En collaboration avec Michel Mendès France. MR 0417077
- 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), no. 3, 249–273. MR 880461, DOI 10.1016/0022-314X(87)90031-X
- James L. Hafner and Kevin S. McCurley, A rigorous subexponential algorithm for computation of class groups, J. Amer. Math. Soc. 2 (1989), no. 4, 837–850. MR 1002631, DOI 10.1090/S0894-0347-1989-1002631-0
- David S. Johnson, The NP-completeness column: an ongoing guide, J. Algorithms 5 (1984), no. 2, 284–299. MR 744495, DOI 10.1016/0196-6774(84)90032-4
- J. C. Lagarias, Worst-case complexity bounds for algorithms in the theory of integral quadratic forms, J. Algorithms 1 (1980), no. 2, 142–186. MR 604862, DOI 10.1016/0196-6774(80)90021-8
- 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), no. 3, 271–296. MR 553223, DOI 10.1007/BF01390234
- J. C. Lagarias and A. M. Odlyzko, Effective versions of the Chebotarev density theorem, Algebraic number fields: $L$-functions and Galois properties (Proc. Sympos., Univ. Durham, Durham, 1975) Academic Press, London, 1977, pp. 409–464. MR 0447191
- Serge Lang, Algebraic number theory, Addison-Wesley Publishing Co., Inc., Reading, Mass.-London-Don Mills, Ont., 1970. MR 0282947
- A. K. Lenstra, Factorization of polynomials, Computational methods in number theory, Part I, Math. Centre Tracts, vol. 154, Math. Centrum, Amsterdam, 1982, pp. 169–198. MR 700263
- A. K. Lenstra, Fast and rigorous factorization under the generalized Riemann hypothesis, Nederl. Akad. Wetensch. Indag. Math. 50 (1988), no. 4, 443–454. MR 976527
- A. K. Lenstra and H. W. Lenstra Jr., Algorithms in number theory, Handbook of theoretical computer science, Vol. A, Elsevier, Amsterdam, 1990, pp. 673–715. MR 1127178 A. K. Lenstra, H. W. Lenstra, Jr., M. S. Manasse, and J. M. Pollard, The factorization of the ninth Fermat number, in preparation. —, 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.
- H. W. Lenstra Jr., Factoring integers with elliptic curves, Ann. of Math. (2) 126 (1987), no. 3, 649–673. MR 916721, DOI 10.2307/1971363
- H. W. Lenstra Jr., On the calculation of regulators and class numbers of quadratic fields, Number theory days, 1980 (Exeter, 1980) London Math. Soc. Lecture Note Ser., vol. 56, Cambridge Univ. Press, Cambridge, 1982, pp. 123–150. MR 697260 —, Primality testing algorithms, Séminaire Bourbaki 33, exp. no. 576, Lecture Notes in Math., vol. 901, Springer-Verlag, Heidelberg, 1981, pp. 243-257.
- H. W. Lenstra Jr. and R. Tijdeman (eds.), Computational methods in number theory. Part I, Mathematical Centre Tracts, vol. 154, Mathematisch Centrum, Amsterdam, 1982. MR 700254
- Carl Pomerance, Fast, rigorous factorization and discrete logarithm algorithms, Discrete algorithms and complexity (Kyoto, 1986) Perspect. Comput., vol. 15, Academic Press, Boston, MA, 1987, pp. 119–143. MR 910929
- C.-P. Schnorr and H. W. Lenstra Jr., A Monte Carlo factoring algorithm with linear storage, Math. Comp. 43 (1984), no. 167, 289–311. MR 744939, DOI 10.1090/S0025-5718-1984-0744939-5
- H. Zantema, Class numbers and units, Computational methods in number theory, Part II, Math. Centre Tracts, vol. 155, Math. Centrum, Amsterdam, 1982, pp. 213–234. MR 702518 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.
- Martin Seysen, A probabilistic factorization algorithm with quadratic forms of negative discriminant, Math. Comp. 48 (1987), no. 178, 757–780. MR 878705, DOI 10.1090/S0025-5718-1987-0878705-X
- Brigitte Vallée, Generation of elements with small modular squares and provably fast integer factoring algorithms, Math. Comp. 56 (1991), no. 194, 823–849. MR 1068808, DOI 10.1090/S0025-5718-1991-1068808-2
- Douglas H. Wiedemann, Solving sparse linear equations over finite fields, IEEE Trans. Inform. Theory 32 (1986), no. 1, 54–62. MR 831560, DOI 10.1109/TIT.1986.1057137
Bibliographic Information
- © Copyright 1992 American Mathematical Society
- Journal: J. Amer. Math. Soc. 5 (1992), 483-516
- MSC: Primary 11Y05; Secondary 11E41, 11Y35, 11Y40
- DOI: https://doi.org/10.1090/S0894-0347-1992-1137100-0
- MathSciNet review: 1137100