Special Number Field Sieve - Overview of Method

Overview of Method

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:

• First, find a large number of multiplicative relations among a factor base of elements of Z/nZ, such that the number of multiplicative relations is larger than the number of elements in the factor base.
• Second, multiply together subsets of these relations in such a way that all the exponents are even, resulting in congruences of the form a2≡b2 (mod n). These in turn immediately lead to factorizations of n: n=gcd(a+b,n)×gcd(a-b,n). If done right, it is almost certain that at least one such factorization will be nontrivial.

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.