In number theory, the general number field sieve (GNFS) is the most efficient classical algorithm known for factoring integers larger than 10100. Heuristically, its complexity for factoring an integer n (consisting of ⌊log2n⌋ + 1 bits) is of the form
in O and L-notations.[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 (which are trivial to factor by taking roots).
The principle of the number field sieve (both special and general) can be understood as an improvement to the simpler rational sieve or quadratic sieve. When using such algorithms to factor a large number n, it is necessary to search for smooth numbers (i.e. numbers with small prime factors) of order n1/2. The size of these values is exponential in the size of n (see below). The general number field sieve, on the other hand, manages to search for smooth numbers that are subexponential in the size of n. Since these numbers are smaller, they are more likely to be smooth than the numbers inspected in previous algorithms. This is the key to the efficiency of the number field sieve. 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.
The size of the input to the algorithm is log2n or the number of bits in the binary representation of n. Any element of the order nc for a constant c is exponential in log n. The running time of the number field sieve is super-polynomial but sub-exponential in the size of the input.
^Pomerance, Carl (December 1996). "A Tale of Two Sieves" (PDF). Notices of the AMS. Vol. 43, no. 12. pp. 1473–1485.
and 25 Related for: General number field sieve information
In number theory, the generalnumberfieldsieve (GNFS) is the most efficient classical algorithm known for factoring integers larger than 10100. Heuristically...
In number theory, a branch of mathematics, the special numberfieldsieve (SNFS) is a special-purpose integer factorization algorithm. The general number...
quadratic sieve algorithm (QS) is an integer factorization algorithm and, in practice, the second-fastest method known (after the generalnumberfieldsieve)....
the rational sieve is a general algorithm for factoring integers into prime factors. It is a special case of the generalnumberfieldsieve. While it is...
mathematics the Function FieldSieve is one of the most efficient algorithms to solve the Discrete Logarithm Problem (DLP) in a finite field. It has heuristic...
in number theory Mahler's theorem Brun sieve Function fieldsieveGeneralnumberfieldsieve Large sieve Larger sieve Quadratic sieve Selberg sieve Sieve...
mathematician, though describing the sieving by odd numbers instead of by primes. One of a number of prime numbersieves, it is one of the most efficient...
factored into two 75-digit primes by Aoki et al. in 2004 using the generalnumberfieldsieve (GNFS), years after bigger RSA numbers that were still part of...
Sieve theory is a set of general techniques in number theory, designed to count, or more realistically to estimate the size of, sifted sets of integers...
prime. A prime sieve or prime numbersieve is a fast type of algorithm for finding primes. There are many prime sieves. The simple sieve of Eratosthenes...
mathematics, the sieve of Atkin is a modern algorithm for finding all prime numbers up to a specified integer. Compared with the ancient sieve of Eratosthenes...
fastest known integer factorization algorithms, for example: Generalnumberfieldsieve algorithm), the VSH hash function is another example of a constructive...
such cases other methods are used such as the quadratic sieve and the generalnumberfieldsieve (GNFS). Because these methods also have superpolynomial...
simple conceptual basis in number theory. It is especially suited to quick hand computation for small bounds. Whereas the sieve of Eratosthenes marks off...
faster than the best-known classical algorithm for factoring, the generalnumberfieldsieve. Grover's algorithm runs quadratically faster than the best possible...
speed up the sieving step of the general numberfieldsieve integer factorization algorithm. During the sieving step, the algorithm searches for numbers...
In mathematics, the sieve of Sundaram is a variant of the sieve of Eratosthenes, a simple deterministic algorithm for finding all the prime numbers up...
P. Buhler; Peter Stevenhagen, eds. (2008). Algorithmic Number Theory: Lattices, NumberFields, Curves and Cryptography. MSRI Publications. Vol. 44. Cambridge...
system is a system of rapid mental calculation. The system consists of a number of readily memorized operations that allow one to perform arithmetic computations...
size of the group). Baby-step giant-step Function fieldsieve Index calculus algorithm Numberfieldsieve Pohlig–Hellman algorithm Pollard's rho algorithm...
Solovay–Strassen are more commonly used. In general, if n {\displaystyle n} is a composite number that is not a Carmichael number, then at least half of all a ∈ (...
some prime p {\displaystyle p} , the state-of-art algorithms are the NumberFieldSieve for Discrete Logarithms, L q [ 1 / 3 , 64 / 9 3 ] {\textstyle L_{q}\left[1/3...
Global Information![{\displaystyle {\begin{aligned}&\exp \left(\left((64/9)^{1/3}+o(1)\right)\left(\log n\right)^{1/3}\left(\log \log n\right)^{2/3}\right)\\[5pt]={}&L_{n}\left[1/3,(64/9)^{1/3}\right]\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/65ab1aa7e793022d23ae984155302c620ebe2ff3)