Сандық есептеулердегі ерекше сан алаңы торы

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 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:
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.

Not every number is an appropriate choice for the SNFS: one needs to know in advance a polynomial f of appropriate degree (the optimal degree is conjectured to be , which is 4, 5, or 6 for the sizes of N currently feasible to factorise) with small coefficients, and a value x such that where N is the number to factorise. There is an extra condition: x must satisfy for a and b no bigger than
One set of numbers for which such polynomials exist are the numbers from the Cunningham tables; for example, when NFSNET factored 1=3^{479}+1, they used the polynomial 1=x^6+3 with 1=x=3^{80} , since 1=(3^{80})^6+3 = 3^{480}+3, and
Numbers defined by linear recurrences, such as the Fibonacci and Lucas numbers, also have SNFS polynomials, but these are a little more difficult to construct. For example, has polynomial , and the value of x satisfies
If one already knows some factors of a large number compatible with SNFS, then one could do the SNFS calculation modulo the remaining part; for the NFSNET example above, 1=3^{479}+1 = (2^2 \times 158071 \times 7167757 \times 7759574882776161031) times a 197 digit composite number (the small factors were found by ECM), and the SNFS was performed modulo the 197 digit number. The number of relations required by SNFS still depends on the size of the large number, but the individual calculations are quicker modulo the smaller number.

This algorithm, as mentioned above, is very efficient for numbers of the form re±s, for r and s relatively small. It is also efficient for any integers which can be represented as a polynomial with small coefficients. This includes integers of the more general form are±bsf, and also for many integers whose binary representation has low Hamming weight. The reason for this is as follows: The Number Field Sieve performs sieving in two different fields. The first field is usually the rationals. The second is a higher degree field. The efficiency of the algorithm strongly depends on the norms of certain elements in these fields. When an integer can be represented as a polynomial with small coefficients, the norms that arise are much smaller than those that arise when an integer is represented by a general polynomial. The reason is that a general polynomial will have much larger coefficients, and the norms will be correspondingly larger. The algorithm attempts to factor these norms over a fixed set of prime numbers. When the
norms are smaller, these numbers are more likely to factor.