= 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
