×

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].

MSC:

11Y05 Factorization
11Y40 Algebraic number theory computations
PDFBibTeX XMLCite