In mathematics, the general number field sieve is the most efficient algorithm known for factoring integers. It uses O(exp( ((64/9) n)1/3 (log n)2/3 )) steps to factor integer n.
It is an improvement of older sieving method which factors n by finding numbers ki such that ri=ki2-n factor completely over a fixed set (called basis) of small primes. Then, having enough such ri - which are called smooth relative to the chosen basis of primes, using Gauss elimination method of linear algebra we can choose exponents ci equal to 0 or 1 such that product of rici is a square, say x2. On the other hand, if the product of kici is y, then x2-y2 is divisible by n and with probability at least one half we get a factor of n by finding greatest common divisor of n and x-y. In this method, the idea was to choose ki close to the square root of n - then ri is of the order of magnitude of square root of n too and there are enough smooth values there.
The general number field sieve''' works as follows:
- We choose two irreducible polynomials f(x) and g(x) with common root m mod n - it is not known what is the best way to choose the polynomials, but usually it is done by picking a degree d for a polynomial and considering expansion of n in basis m where m is of order n1/d. The point is to get coefficients of f and g as small as possible - they will be of order of m, while having small degrees d and e of our polynomials.
- Now, we consider number field rings Z[r1] and Z[r2] where r1 and r2 are roots of polynomials f and g, and look for values a and b such that r=bd*f(a/b) and s=be*g(a/b) are smooth relative to the chosen basis of primes. If a and b are small, r and s will be too (but at least of order of m), and we have a better chance for them to be smooth at the same time.
- Having enough such pairs, using Gauss elimination method we can get products of certain r and of corresponding s to be squares at the same time. We need a slightly stronger condition - that they are norms of squares in our number fields, but we can get that condition by this method too. Each r is a norm of a- r1*b and hence we get that product of corresponding factors a- r1*b is a square in Z[r1], with a "square root" which can be determined (as a product of known factors in Z[r1]) - it will typically be represented as a nonrational algebraic number. Similary we get that product of factors a- r2*b is a square in Z[r2], with a "square root" which we can also compute.
- Since m is root of both f and g mod n, there are homomorphisms from the rings Z[r1] and Z[r2] to the ring Z/nZ, which map r1 and r2 to m, and these homomorphisms will map each "square root" (typically not represented as a rational number) into its integer representative. Now product of factors a-m*b mod n we can get as a square in two ways - one for each homomorphism. Thus, we get two numbers x and y, with x2-y2 divisible by n and again with probability at least one half we get a factor of n by finding greatest common divisor of n and x-y