Encyclopedia > General Number Field Sieve

  Article Content

General Number Field Sieve

General Number Field Sieve is the most efficient algorithm known for factoring integers. It uses θ(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, 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

The second best known algorithm for integer factorization is the Lenstra Elliptic Curve Factorization method. It is better than the General Number Field Sieve when factors are of small size, as it works by finding smooth values of order of the smallest prime divisor of n, and its running time depends on the size of this divisor.



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Reformed churches

... Helvetic Confession[?], Westminster Confession of Faith[?], Westminster Shorter Catechism[?], Westminster Larger Catechism[?], Theological Declaration of Barmen[?], ...

 
 
 
This page was created in 76 ms