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