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, the integer factorization problem is the problem of finding a non-trivial divisor of a composite number; for example, given a number like 91, the challenge is to find a number such as 7 which divides it. ... In mathematics, the general number field sieve (GNFS) is the most efficient algorithm known for factoring integers larger than 100 digits. ...

The special number field sieve is efficient for integers of the form r^e ± s, where r and s are small. In particular, it is ideal for factoring Fermat numbers. In mathematics, a Fermat number, named after Pierre de Fermat who first studied them, is a positive integer of the form where n is a nonnegative integer. ...

Its running time and space complexity, in asymptotic notation, is conjectured to be: Big O notation or Big Oh notation, and also Landau notation or asymptotic notation, is a mathematical notation used to describe the asymptotic behavior of functions. ...

The SNFS has been used extensively by NFSNET (a volunteer distributed computing effort) and others to factorise numbers of the Cunningham project; for some time the records for integer factorisation have been numbers factored by SNFS. Distributed computing is a method of computer processing in which different parts of a program run simultaneously on two or more computers that are communicating with each other over a network. ... The Cunningham project aims to find factors of large numbers of the form bn ± 1 for b = 2, 3, 5, 6, 7, 10, 11, 12 and large exponents n. ... The first very large distributed factorisation was RSA129, a challenge number described in the Scientific American article of 1977 which first popularised the RSA cryptosystem. ...

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. In mathematics, the rational sieve is a general algorithm for factoring integers into prime factors. ... In mathematics, the rational sieve is a general algorithm for factoring integers into prime factors. ...

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: In mathematics, the rational sieve is a general algorithm for factoring integers into prime factors. ...

• 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 a²≡b² (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. Modular arithmetic (sometimes called modulo arithmetic, or clock arithmetic because of its use in the 24-hour clock system) is a system of arithmetic for integers, where numbers wrap around after they reach a certain value — the modulus. ... Look up mod in Wiktionary, the free dictionary. ... The three letter acronym GCD may refer to: Greatest common divisor — in mathematics Great circle distance — in navigation Griffith College Dublin — private college in Ireland Grand Comic-Book Database — database of comic book information Global Communications Devices — supplier of semiconductor devices used in wireless networking Gardner Carton & Douglas — a US... In mathematics, the rational sieve is a general algorithm for factoring integers into prime factors. ... Linear algebra is the branch of mathematics concerned with the study of vectors, vector spaces (also called linear spaces), linear maps (also called linear transformations), and systems of linear equations. ... In computer science, efficiency is used to describe several desirable properties of an algorithm or other construct, besides clean design, functionality, etc. ... In mathematics, an algebraic number field (or simply number field) is a finite-dimensional (and therefore algebraic) field extension of the rational numbers Q. That is, it is a field which contains Q and has finite dimension, or degree, when considered as a vector space over Q. The study of...

Details of method

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. In mathematics, the adjective irreducible means that an object cannot be expressed as a product of at least two non-trivial factors in a given ring. ... Look up mod in Wiktionary, the free dictionary. ... In mathematics, a root (or a zero) of a function f is an element x in the domain of f such that f(x) = 0. ... In mathematics, a ring is an algebraic structure in which addition and multiplication are defined and have properties listed below. ... The integers are commonly denoted by the above symbol. ... In abstract algebra, a ring homomorphism is a function between two rings which respects the operations of addition and multiplication. ... Modular arithmetic (sometimes called modulo arithmetic, or clock arithmetic because of its use in the 24-hour clock system) is a system of arithmetic for integers, where numbers wrap around after they reach a certain value — the modulus. ... In mathematics, a unique factorization domain (UFD) is, roughly speaking, a commutative ring in which every element can be uniquely written as a product of prime elements, analogous to the fundamental theorem of arithmetic for the integers. ...

Next, we set up two parallel factor bases, one in Z[α] and one in Z. The one in Z[α] consists of all the prime ideals in Z[α] whose norm is bounded by a chosen value N_max. 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: In mathematics, the integers a and b are said to be coprime or relatively prime if and only if they have no common factor other than 1 and −1, or equivalently, if their greatest common divisor is 1. ...

• 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[α]; given how we chose the factor base, this is equivalent to the norm of a+bα being divisible only by primes less than N_max.

These pairs are found through a sieving process, analogous to the Sieve of Eratosthenes; this motivates the name "Number Field Sieve". In number theory, a positive integer m is called B-smooth if all prime factors of m are such that . For example, 22335654 is 5-smooth since none of its prime factors are greater than 5. ... In mathematics, the Sieve of Eratosthenes is a simple, ancient algorithm for finding all prime numbers up to a specified integer. ...

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.

Choice of parameters

Not every number is an appropriate choice for the SNFS: you need 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 N^{1 / d}.

One set of numbers for which such polynomials exist are the numbers from the Cunningham tables; for example, when NFSNET factored 3^479+1, they used the polynomial x^6+3 with x=3^80, since (3^80)^6+3 = 3^480+3 is definitely divisible by 3^479+1. The Cunningham project aims to find factors of large numbers of the form bn ± 1 for b = 2, 3, 5, 6, 7, 10, 11, 12 and large exponents n. ...

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, F₇₀₉ has polynomial n⁵ + 10n³ + 10n² + 10n + 3, and the value of x satisfies F₁₄₂x − F₁₄₁ = 0.^[1] A tiling with squares whose sides are successive Fibonacci numbers in length A Fibonacci spiral, created by drawing arcs connecting the opposite corners of squares in the Fibonacci tiling shown above - see golden spiral. ... The Lucas numbers are an integer sequence named after the mathematician François Édouard Anatole Lucas (1842–1891), who studied both that sequence and the closely related Fibonacci numbers. ...

If you already know some factors of a large SNFS-number, you can do the SNFS calculation modulo the remaining part; for the NFSNET example above, 3^479+1 = (4*158071*7167757*7759574882776161031) times a 197-digit composite number (the small factors were removed 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. The Lenstra elliptic curve factorization is a fast, but still sub-exponential running time, algorithm for integer factorization which employs elliptic curves. ...

Limitations of algorithm

This algorithm, as mentioned above, is very efficient for numbers of the form r^e±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 a'r^e±b's^f, 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.

External links

• http://www.nfsnet.org/

• http://modular.fas.harvard.edu/129-05/final_papers/Steve_Byrnes.pdf

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