Number body sieve

The number field sieve (English sieve number field , 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 over 100 digits that could not be broken down by other methods. Typically, several 100 computers are operated in parallel .

History of origin

In 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 method for very special numbers. In this letter he illustrated this procedure using the Fermat number F ₇ and assumed that the number F _9, which has not yet been factored, may be a candidate for this procedure. But Pollard did not yet use a sieving method in the algebraic number field .

In the following years, this idea was developed by, among others, Arjen Lenstra , HW Lenstra, Mark Manasse and John M. Pollard . This resulted in the special number body sieve (as the process is called today in order to be able to differentiate it from the general number body sieve). The special number field sieve can only be used for numbers of the form with b , r small and m large. ${\displaystyle b^{m}-r}$

The general number body sieve was found at approximately the same time as the special number body sieve by Joe Buhler , HW Lenstra and Carl Pomerance . This can be used for any number, but you have to accept losses in speed.

In 1990 F _{9 was} factorized with the help of the special number field sieve .

In 1991, Pollard published a variant of the number body sieve in which a two-dimensional sieve is used, which he calls a mesh sieve. With this mesh screen variant, combined with other methods, a 200-digit decimal number (called RSA-200) was factored from 2003 to 2005.

functionality

The number body sieve can be understood as a generalization of the square sieve . A key consideration here is that even numbers may occur more frequently in other monoids than and thus could be found more quickly. ${\displaystyle \mathbb {Z} }$

Asymptotic running time

The asymptotic running time of the number field sieve has not yet been proven exactly. Under some assumptions applicable than likely, however, you can this for a number n to

${\displaystyle e^{(C+o(1))(\log n)^{\frac {1}{3}}(\log \log n)^{\frac {2}{3}}}}$

to calculate. This means that the running time is sub-exponential, but still superpolynomial, of the length of the number n . The constant C depends on whether the special or the general number field sieve is used:

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

literature

• Carl Pomerance: A Tale of Two Sieves , Notices of the AMS, 43 (1996) 1473–1485 (Web version:  http://www.ams.org/notices/199612/pomerance.pdf )
• AK Lenstra, HW Lenstra, Jr .: The development of the number field sieve , Lecture Notes in Mathematics, V. 1554, 1993

Web links

• http://www.cdc.informatik.tu-darmstadt.de/~samoa/NFS.pdf - The Number Field Sieve: Development, Variants and Successes by Katja Schmidt-Samoa. (PDF file; 1.16 MB)

Individual evidence

1. ↑ Fermat factoring status. Archived from the original on February 10, 2016 ; accessed on November 1, 2015 .  
2. ↑ Announcement of the factorization of RSA-200 ( Memento of the original from March 22, 2008 in the Internet Archive ) Info: The archive link was inserted automatically and not yet checked. Please check the original and archive link according to the instructions and then remove this notice. .