General number field sieve

From Wikipedia, the free encyclopedia

In mathematics, the general number field sieve (GNFS) is the most efficient classical algorithm known for factoring integers larger than 100 digits. Heuristically, its complexity for factoring an integer n (consisting of logn bits) is of the form

(in O and L notations) for a constant c which depends on the complexity measure and on the variant of the algorithm^[1]. 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 n^1/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.

Note that logn is the number of digits in the binary representation of n, that is the size of the input to the algorithm. The (worst-case) running time is therefore super-polynomial in the size of the input. It is an important open problem whether factorization can be done in reasonable time - polynomial time - on a classical computer. Conversely, it is known that factorization is a tractable problem, using algorithms such as Shor's algorithm, in polynomial time, on a suitable quantum computer.

[edit] Method

We choose two polynomials f(x) and g(x) of small degrees d and e, which have integer coefficients, which are irreducible over the rationals, and which, when interpreted mod n, have a common root m. An optimal strategy for choosing these polynomials is not known; one simple method is to pick a degree d for a polynomial, consider the expansion of n in base m (allowing digits between -m and m) for a number of different m of order n^1/d, and pick f(x) as the polynomial with the smallest coefficients and g(x) as x-m.

A better method was suggested by Murphy and Brent ^[2]; they introduce a two-part score for polynomials, based on the presence of roots modulo small primes and on the average value that the polynomial takes over the sieving area.

The best reported results [2] were achieved by the method of Thorsten Kleinjung ^[3], which allows g(x) = ax+b, and searches over a composed of small prime factors congruent to 1 modulo 2d and over leading coefficients of f which are divisible by 60.

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 = b^d·f(a/b) and s = b^e·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. The current best-known approach for this search is lattice sieving; to get acceptable yields, it is necessary to use a large factor base, and generally sieving with large primes is used.

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 an irrational 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 x²-y² 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

Most implementations are split three ways: polynomial selection, sieving, and final processing. A working implementation of GNFS is a reasonable master's thesis, and a few such theses have been written, but full production-scale implementations are rather more work.

The gold-standard implementation until 2007 was a suite of software developed and distributed by CWI in the Netherlands, which was available only under a relatively restrictive license; in 2007, Jason Papadopoulos developed a faster implementation of final processing as part of msieve, which is public-domain. msieve, however, can only run on a single SMP computer, whilst CWI's implementation can be distributed among several nodes in a cluster with a sufficiently fast interconnect.

Polynomial selection is normally performed by GPL software written by Kleinjung, and lattice sieving by GPL software written by Franke and Kleinjung; these are distributed in GGNFS.

• GGNFS.
• pGNFS
• factor by gnfs
• msieve, which contains excellent final-processing code, and implementations of the polynomial selection and sieving parts.

[edit] References

v • d • e Number-theoretic algorithms Primality tests AKS · APR · Ballie-PSW · ECPP · Fermat · Lucas–Lehmer · Lucas–Lehmer (Mersenne numbers) · Lucas–Lehmer–Riesel · Proth's theorem · Pépin's · Solovay-Strassen · Miller-Rabin · Trial division Sieving algorithms Sieve of Atkin · Sieve of Eratosthenes · Sieve of Sundaram · Wheel factorization Integer factorization algorithms CFRAC · Dixon's · ECM · Euler's · Pollard's rho · P - 1 · P + 1 · QS · GNFS · SNFS · rational sieve · Fermat's · Shanks' square forms · Trial division · Shor's algorithm Other algorithms Ancient Egyptian multiplication · Aryabhata · Binary GCD · Chakravala · Euclidean · Extended Euclidean · integer relation algorithm · integer square root · Modular exponentiation · Shanks-Tonelli Italics indicate that algorithm is for numbers of special forms; bold indicates deterministic algorithm for primality tests.