A rigorous time bound for factoring integers

Lenstra, H. W. ; Pomerance, Carl

Journal of the American Mathematical Society, Tome 05 (1992) no. 3, pp. 483-516

Résumé

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.

Détail

DOI : 10.1090/S0894-0347-1992-1137100-0

Bibliographie

[1] Adleman, Leonard M., Pomerance, Carl, Rumely, Robert S. On distinguishing prime numbers from composite numbers Ann. of Math. (2) 1983 173 206

[2] Brent, Richard P. Fast multiple-precision evaluation of elementary functions J. Assoc. Comput. Mach. 1976 242 251

[3] Canfield, E. R., Erdå‘S, Paul, Pomerance, Carl On a problem of Oppenheim concerning “factorisatio numerorum” J. Number Theory 1983 1 28

[4] Coppersmith, Don Modifications to the number field sieve J. Cryptology 1993 169 180

[5] Cox, David A. Primes of the form 𝑥²+𝑛𝑦² 1989

[6] Davenport, Harold Multiplicative number theory 1980

[7] Dixon, John D. Asymptotically fast factorization of integers Math. Comp. 1981 255 260

[8] Ellison, William John Les nombres premiers 1975

[9] Friedlander, J. B., Lagarias, J. C. On the distribution in short intervals of integers having no large prime factor J. Number Theory 1987 249 273

[10] Hafner, James L., Mccurley, Kevin S. A rigorous subexponential algorithm for computation of class groups J. Amer. Math. Soc. 1989 837 850

[11] Johnson, David S. The NP-completeness column: an ongoing guide J. Algorithms 1984 284 299

[12] Lagarias, J. C. Worst-case complexity bounds for algorithms in the theory of integral quadratic forms J. Algorithms 1980 142 186

[13] Lagarias, J. C., Montgomery, H. L., Odlyzko, A. M. A bound for the least prime ideal in the Chebotarev density theorem Invent. Math. 1979 271 296

[14] Lagarias, J. C., Odlyzko, A. M. Effective versions of the Chebotarev density theorem 1977 409 464

[15] Lang, Serge Algebraic number theory 1970

[16] Lenstra, A. K. Factorization of polynomials 1982 169 198

[17] Lenstra, A. K. Fast and rigorous factorization under the generalized Riemann hypothesis Nederl. Akad. Wetensch. Indag. Math. 1988 443 454

[18] Lenstra, A. K., Lenstra, H. W., Jr. Algorithms in number theory 1990 673 715

[19] Lenstra, H. W., Jr. Factoring integers with elliptic curves Ann. of Math. (2) 1987 649 673

[20] Lenstra, H. W., Jr. On the calculation of regulators and class numbers of quadratic fields 1982 123 150

[21] Computational methods in number theory. Part I 1982

[22] Pomerance, Carl Fast, rigorous factorization and discrete logarithm algorithms 1987 119 143

[23] Schnorr, C.-P., Lenstra, H. W., Jr. A Monte Carlo factoring algorithm with linear storage Math. Comp. 1984 289 311

[24] Zantema, H. Class numbers and units 1982 213 234

[25] Seysen, Martin A probabilistic factorization algorithm with quadratic forms of negative discriminant Math. Comp. 1987 757 780

[26] Vallã©E, Brigitte Generation of elements with small modular squares and provably fast integer factoring algorithms Math. Comp. 1991 823 849

[27] Wiedemann, Douglas H. Solving sparse linear equations over finite fields IEEE Trans. Inform. Theory 1986 54 62