×

A rigorous time bound for factoring integers. (English) Zbl 0770.11057

Authors’ 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\bigl[{1\over 2},1+o(1)\bigr]\) for \(n\to\infty\), where \(L_ x[a,b]=\exp(b(\log x)^ a(\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\bigl[{1\over 3},O(1)\bigr]\).
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\bigl[{1\over 2},1+o(1)\bigr]\) 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.

MSC:

11Y05 Factorization
11R44 Distribution of prime ideals
11N25 Distribution of integers with specified multiplicative constraints
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] 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. · Zbl 0526.10004 · doi:10.2307/2006975
[2] Z. I. Borevič and I. R. Šafarevič, Teorija čisel, Izdat. “Nauka”, Moscow, 1964; English transl., Number theory, Academic Press, New York, 1966.
[3] Richard P. Brent, Fast multiple-precision evaluation of elementary functions, J. Assoc. Comput. Mach. 23 (1976), no. 2, 242 – 251. · Zbl 0324.65018 · doi:10.1145/321941.321944
[4] J. P. Buhler, H. W. Lenstra, Jr., and C. Pomerance, Factoring integers with the number field sieve, in preparation. · Zbl 0806.11067
[5] 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. · Zbl 0513.10043 · doi:10.1016/0022-314X(83)90002-1
[6] Don Coppersmith, Modifications to the number field sieve, J. Cryptology 6 (1993), no. 3, 169 – 180. · Zbl 0806.11071 · doi:10.1007/BF00198464
[7] David A. Cox, Primes of the form \?²+\?\?², A Wiley-Interscience Publication, John Wiley & Sons, Inc., New York, 1989. Fermat, class field theory and complex multiplication.
[8] Harold Davenport, Multiplicative number theory, 2nd ed., Graduate Texts in Mathematics, vol. 74, Springer-Verlag, New York-Berlin, 1980. Revised by Hugh L. Montgomery. · Zbl 0453.10002
[9] P. G. Lejeune Dirichlet and R. Dedekind, Vorlesungen über Zahlentheorie, 4th ed., Vieweg, Braunschweig, 1893; reprint, Chelsea, New York, 1968.
[10] John D. Dixon, Asymptotically fast factorization of integers, Math. Comp. 36 (1981), no. 153, 255 – 260. · Zbl 0452.10010
[11] William John Ellison, Les nombres premiers, Hermann, Paris, 1975 (French). En collaboration avec Michel Mendès France; Publications de l’Institut de Mathématique de l’Université de Nancago, No. IX; Actualités Scientifiques et Industrielles, No. 1366. · Zbl 0313.10001
[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), no. 3, 249 – 273. · Zbl 0606.10033 · doi:10.1016/0022-314X(87)90031-X
[13] 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. · Zbl 0702.11088
[14] David S. Johnson, The NP-completeness column: an ongoing guide, J. Algorithms 5 (1984), no. 2, 284 – 299. , https://doi.org/10.1016/0196-6774(84)90032-4 David S. Johnson, The NP-completeness column: an ongoing guide, J. Algorithms 5 (1984), no. 3, 433 – 447. · Zbl 0547.68048 · doi:10.1016/0196-6774(84)90022-1
[15] J. C. Lagarias, Worst-case complexity bounds for algorithms in the theory of integral quadratic forms, J. Algorithms 1 (1980), no. 2, 142 – 186. · Zbl 0473.68030 · doi:10.1016/0196-6774(80)90021-8
[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), no. 3, 271 – 296. · Zbl 0401.12014 · doi:10.1007/BF01390234
[17] J. C. Lagarias and A. M. Odlyzko, Effective versions of the Chebotarev density theorem, Algebraic number fields: \?-functions and Galois properties (Proc. Sympos., Univ. Durham, Durham, 1975) Academic Press, London, 1977, pp. 409 – 464. · Zbl 0362.12011
[18] Serge Lang, Algebraic number theory, Addison-Wesley Publishing Co., Inc., Reading, Mass.-London-Don Mills, Ont., 1970. · Zbl 0211.38404
[19] 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.
[20] A. K. Lenstra, Fast and rigorous factorization under the generalized Riemann hypothesis, Nederl. Akad. Wetensch. Indag. Math. 50 (1988), no. 4, 443 – 454. · Zbl 0669.10012
[21] 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. · Zbl 0900.68250
[22] A. K. Lenstra, H. W. Lenstra, Jr., M. S. Manasse, and J. M. Pollard, The factorization of the ninth Fermat number, in preparation. · Zbl 0792.11055
[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. · Zbl 0715.30009
[24] H. W. Lenstra Jr., Factoring integers with elliptic curves, Ann. of Math. (2) 126 (1987), no. 3, 649 – 673. · Zbl 0629.10006 · doi:10.2307/1971363
[25] 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.
[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 , Computational methods in number theory. Part I, Mathematical Centre Tracts, vol. 154, Mathematisch Centrum, Amsterdam, 1982. · Zbl 0497.00005
[28] 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. · Zbl 0659.10003
[29] C.-P. Schnorr and H. W. Lenstra Jr., A Monte Carlo factoring algorithm with linear storage, Math. Comp. 43 (1984), no. 167, 289 – 311. · Zbl 0559.10004
[30] 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. R. J. Schoof, Quadratic fields and factorization, Computational methods in number theory, Part II, Math. Centre Tracts, vol. 155, Math. Centrum, Amsterdam, 1982, pp. 235 – 286.
[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. · JFM 46.0266.01
[32] Martin Seysen, A probabilistic factorization algorithm with quadratic forms of negative discriminant, Math. Comp. 48 (1987), no. 178, 757 – 780. · Zbl 0619.10004
[33] Brigitte Vallée, Generation of elements with small modular squares and provably fast integer factoring algorithms, Math. Comp. 56 (1991), no. 194, 823 – 849. · Zbl 0724.11067
[34] Douglas H. Wiedemann, Solving sparse linear equations over finite fields, IEEE Trans. Inform. Theory 32 (1986), no. 1, 54 – 62. · Zbl 0607.65015 · doi:10.1109/TIT.1986.1057137
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.