Special number field sieve

In number theory, a branch of mathematics, the special number field sieve (SNFS) is a special-purpose integer factorization algorithm. The general number field sieve (GNFS) was derived from it.

The special number field sieve is efficient for integers of the form r^e ± s, where r and s are small (for instance Mersenne numbers).

Heuristically, its complexity for factoring an integer ${\displaystyle n}$ is of the form:^[1]

${\displaystyle \exp \left(\left(1+o(1)\right)\left({\tfrac {32}{9}}\log n\right)^{1/3}\left(\log \log n\right)^{2/3}\right)=L_{n}\left[1/3,(32/9)^{1/3}\right]}$

in O and L-notations.

The SNFS has been used extensively by NFSNet (a volunteer distributed computing effort), NFS@Home and others to factorise numbers of the Cunningham project; for some time the records for integer factorization have been numbers factored by SNFS.