General number field sieve

The number field sieve (English number field sieve, NFS ) is a term from the mathematical branch of number theory. It is one of the fastest known algorithms for factoring large numbers.

The number field sieve is mainly used for numbers with more than 100 locations that could not be broken down by other methods. Typically, several 100 can be operated in parallel.

Genesis

1988 John M. Pollard wrote a letter to Andrew Odlyzko with copies to Richard P. Brent, John Brillhart, Hendrik Lenstra, Claus -Peter Schnorr and Hiromi Suyama, in which he described a new factorization for special numbers. In this letter, he illustrated this method to the Fermat number F7 and guessed that so that may be a candidate for this procedure to date not yet factored number F9. Pollard used but still no screening process in algebraic number fields.

In subsequent years, this idea, among others, Arjen Lenstra, HW Lenstra, Mark Manasse and John M. Pollard was expanded. The result was the special number field sieve (such as the method is called nowadays in order to distinguish it from the general number field sieve can ). The special number field sieve can be only for numbers of the form b, r apply small and m large.

The general number field sieve was approximately at the same time to special number field sieve by Joe Buhler, HW Lenstra and Carl Pomerance found. This is applicable for any figures, but you have to but sacrifices in speed.

1992 succeeded with the help of special Zahlkörpersiebs the factorization of F9.

As early as 1991 published a variant of the Pollard Zahlkörpersiebs, in a two-dimensional screen is used, which he called a mesh screen. This Gittersiebvariante, combined with other methods, a 200 - digit decimal number was from 2003 to 2005 ( called RSA -200) factored.

Asymptotic running time

The asymptotic running time of the Zahlkörpersiebs could not yet be exactly proved. Under some assumptions applicable than likely you can but this is a number n to

Calculate. So that the duration is sub-exponentially, but still superpolynomial in the length of the number n, the constant C is dependent on whether the special or general number field sieve is used:

• Special number field sieve: C = (32 /9) 1/3
• General number field sieve: C = (64/ 9) 1/3