Special number field sieve
From Wikipedia, the free encyclopedia
- "NFSNET" redirects here. For the unrelated but similarly spelled computer network, see NSFNet.
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. In particular, it is ideal for factoring Fermat numbers.
Its running time and space complexity, in asymptotic notation, is conjectured to be:
The SNFS has been used extensively by NFSNET (a volunteer distributed computing effort) and others to factorise numbers of the Cunningham project.
Contents |
[edit] 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.
[edit] Details of method
Let n be the integer we want to factor. We pick a monic 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 complex 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.
Next, we set up two parallel factor bases, one in Z[α] and one in Z. The one in Z[α] consists of all the primes in Z[α] up to some bound, along with a set of units of Z[α] sufficient to generate the group of units for that set. Meanwhile, the factor base in Z, as in the rational sieve case, consists of all prime integers up to some other bound.
We then search for relatively prime pairs of integers (a,b) such that:
- a+bm is smooth with respect to the factor base in Z (i.e., it is a product of elements in the factor base).
- a+bα is smooth with respect to the factor base in Z[α].
These pairs are found through a sieving process, analogous to the Sieve of Eratosthenes; this motivates the name "Number Field Sieve".
For each such pair, we can apply the ring homomorphism φ to the factorization of a+bα, and we can apply the canonical ring homomorphism from Z to Z/nZ to the factorization of a+bm. Setting these equal gives a multiplicative relation among elements of a bigger factor base in Z/nZ, and if we find enough pairs we can proceed to combine the relations and factor n, as described above.
[edit] Choice of parameters
Let n be the number we want to factor. First, we choose the degree d for the polynomial f. The best value is conjectured to be roughly d=(3 (log n)/(log log n))1/3.
Next, we choose the coefficients of f. Recall that, for the algorithm to be effective, n must be of the form re-s, where s here may be positive or negative. We find the smallest integer k with 
, let t=s×rkd-e, and then define f(x)=xd-e. Finally, we choose m=rk.
[edit] Limitations of algorithm
This algorithm, as mentioned above, is only efficient for numbers of the form re±s, for r and s relatively small. The reason for this is as follows: For arbitrary integers, we can still choose a different f and proceed as above, but in general f will have such large coefficients that the number field Z[α] will be too complicated to perform the required computations in. The difference between SNFS and GNFS is that the latter has slightly different methods of computation that can work in these complicated number fields.
[edit] External links
- A. K. Lenstra, H. W. Lenstra, Jr., M. S. Manasse, and J. M. Pollard, The Factorization of the Ninth Fermat Number, Math. Comp. 61 (1993), 319-349. A draft is available at www.std.org/~msm/common/f9paper.ps.
- A. K. Lenstra, H. W. Lenstra, Jr. (eds.) The Development of the Number Field Sieve, Lecture Notes in Mathematics 1554, Springer-Verlag, New York, 1993.
