General number field sieve

From Wikipedia, the free encyclopedia

You have new messages (last change).

In mathematics, the general number field sieve (GNFS) is the most efficient algorithm known for factoring integers larger than 100 digits. It uses

O\left(\exp\left(\left(\frac{64}{9}\log n\right)^{\frac{1}{3}} (\log \log n)^{\frac{2}{3}}\right)\right)

steps to factor an integer n (see Big O notation). The space complexity scales with the square root of the time complexity. [2] It is a generalization of the special number field sieve: while the latter can only factor numbers of a certain special form, the general number field sieve can factor any number (apart from prime powers, but this is a minor issue). When the term number field sieve (NFS) is used without qualification, it refers to the general number field sieve.

The principle of the number field sieve (both special and general) can be understood as an extension of the simpler rational sieve. When using the rational sieve to factor a large number n, it is necessary to search for smooth numbers (i.e. numbers with small prime factors) of order n; the rarity of these causes the rational sieve to be impractical. The general number field sieve, on the other hand, only requires a search for smooth numbers of order n1/d, where d is some integer greater than one. Since larger numbers are far less likely to be smooth than smaller numbers, this is the key to the efficiency of the number field sieve. But in order to achieve this speed-up, the number field sieve has to perform computations and factorizations in number fields. This results in many rather complicated aspects of the algorithm, as compared to the simpler rational sieve.

[edit] Method

We choose two irreducible polynomials f(x) and g(x) with a common root m mod n; these polynomials will be of order of m, while having small degrees d and e. The best way to choose the polynomials has not been proven, but usually it is done by picking a degree d for a polynomial and considering the expansion of n in basis m where m is of order n1/d. The point is to get the coefficients of f and g as small as possible. Currently the best way is described by Murphy and Brent [1].

Now, we consider the number field rings Z[r1] and Z[r2], where r1 and r2 are roots of the 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, then 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 Gaussian elimination, we can get products of certain r and of the 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 the product of the 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. Similarly, we get that the product of the factors a- r2*b is a square in Z[r2], with a "square root" which we can also compute.

Since m is a 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 the product of the factors a-m*b mod n can be obtained 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 the greatest common divisor of n and x-y.

[edit] Implementations

[edit] References

  1. ^ Murphy, B.; Brent, R. P., On quadratic polynomials for the number field sieve. Australian Computer Science Communications 20 (1998), pp. 199-213. [1]
  • Lenstra, Arjen K.; Lenstra, H.W., Jr. (Eds.) (1993). The development of the number field sieve. Lecture Notes in Math. 1554. Springer-Verlag.
  • Pomerance, Carl (1996). A Tale of Two Sieves. Notices of the AMS 1996, 1473–1485.
  • Crandall, Richard; Pomerance, Carl (2001). Prime Numbers: A Computational Perspective, 1st edition, Springer. ISBN 0-387-94777-9. Section 6.2: Number field sieve, pp.244–267.
Retrieved from "http://en.wikipedia.org../../../g/e/n/General_number_field_sieve.html"
In other languages