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.
Read more about this topic: Special Number Field Sieve
Famous quotes containing the word method:
“The country needs and, unless I mistake its temper, the country demands bold, persistent experimentation. It is common sense to take a method and try it. If it fails, admit it frankly and try another. But above all, try something. The millions who are in want will not stand idly by silently forever while the things to satisfy their needs are within easy reach.”
—Franklin D. Roosevelt (1882–1945)