Buhler, J. P.; Lenstra, H. W. jun.; Pomerance, Carl Factoring integers with the number field sieve. (English) Zbl 0806.11067 Lenstra, A. K. (ed.) et al., The development of the number field sieve. Berlin: Springer-Verlag. Lect. Notes Math. 1554, 50-94 (1993). Summary: In 1990, the ninth Fermat number was factored into primes by means of a new algorithm, the “number field sieve”, which was proposed by John Pollard. The present paper is devoted to the description and analysis of a more general version of the number field sieve. It should be possible to use this algorithm to factor arbitrary integers into prime factors, not just integers of a special form like the ninth Fermat number.Under reasonable heuristic assumptions, the analysis predicts that the time needed by the general number field sieve to factor \(n\) is \(\exp ((c+o(1)) (\log n)^{1/3} (\log\log n)^{2/3})\) (for \(n\to\infty\)), where \(c= (64/9)^{1/3}\doteq 1.9223\). This is asymptotically faster than all other known factoring algorithms, such as the quadratic sieve and the elliptic curve method.For the entire collection see [Zbl 0777.00017]. Cited in 3 ReviewsCited in 46 Documents MSC: 11Y05 Factorization 11Y40 Algebraic number theory computations Keywords:number field sieve; algebraic number fields; factoring algorithms PDFBibTeX XMLCite \textit{J. P. Buhler} et al., Lect. Notes Math. 1554, 50--94 (1993; Zbl 0806.11067)