= General number field sieve
A general-purpose classical <integer factorization> algorithm combining polynomial relations, arithmetic in <number fields> and sparse linear algebra to construct congruent squares modulo the input. Its familiar general-input complexity estimate is heuristic and subexponential in the input's value, roughly $\exp(O(n^{1/3}(\log n)^{2/3}))$ for $n$ input bits. This is not polynomial in the bit length. Special input structure, small factors and preprocessing can make other algorithms preferable.
Back to article page
