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. 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 re ± s, where r and s are small (for instance Mersenne numbers). Heuristically, its complexity for factoring an integer n {displaystyle n} is of the form: 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. The SNFS is based on an idea similar to the much simpler rational sieve; in particular, readers may find it helpful to read about the rational sieve first, before tackling the SNFS. The SNFS works as follows. Let n be the integer we want to factor. As in the rational sieve, the SNFS can be broken into two steps: The second step is identical to the case of the rational sieve, and is a straightforward linear algebra problem. The first step, however, is done in a different, more efficient way than the rational sieve, by utilizing number fields. Let n be the integer we want to factor. We pick an irreducible polynomial f with integer coefficients, and an integer m such that f(m)≡0 (mod n) (we will explain how they are chosen in the next section). Let α be a root of f; we can then form the ring Z. There is a unique ring homomorphism φ from Z to Z/nZ that maps α to m. For simplicity, we'll assume that Z is a unique factorization domain; the algorithm can be modified to work when it isn't, but then there are some additional complications.