User:Decrypt3/NFSTemp

In number theory, the general number field sieve (GNFS) is a general-purpose integer factorization algorithm. At present, it is the asymptotically fastest-known factorization algorithm for a general composite n. GNFS is a generalization of the special number field sieve (SNFS). When the term “number field sieve” is used without qualification, it refers to the GNFS. SNFS was invented by John Pollard in 1988. It was then modified to become GNFS in 1990, using ideas of Joe Buhler, Hendrik Lenstra, Carl Pomerance and Leonard Adleman.

Core ideas

The ultimate goal of GNFS is to set up a congruence of squares, much like other general-purpose factorization algorithms. GNFS uses a monic (first coefficient is one), irreducible polynomial modulo n to define one set of algebraic integers and one set of rational numbers. It then finds squares in both of these sets and uses ring homomorphisms to thereby derive a congruence of squares.

Speed

The GNFS is the asymptotically fastest-known factorization algorithm today. Its time complexity is:

$O\left(\exp \left(c(\log n)^{1/3}(\log \log n)^{2/3}\right)\right)$

When it was invented, the GNFS supplanted the previous general-purpose factorization champion, the quadratic sieve (QS), whose time complexity is:

$O\left(\exp \left({\sqrt {\log n\log \log n}}\right)\right)$.