Special number field sieve

Last updated March 11, 2024

In number theory, a branch of mathematics, the special number field sieve (SNFS) is a special-purpose integer factorization algorithm. The general number field sieve (GNFS) was derived from it.

Overview of method

The SNFS is based on an idea similar to the much simpler rational sieve; in particular, readers may find it helpful to read about the rational sieve first, before tackling the SNFS.

The SNFS works as follows. Let n be the integer we want to factor. As in the rational sieve, the SNFS can be broken into two steps:

First, find a large number of multiplicative relations among a factor base of elements of Z/nZ, such that the number of multiplicative relations is larger than the number of elements in the factor base.
Second, multiply together subsets of these relations in such a way that all the exponents are even, resulting in congruences of the form a²≡b² (mod n). These in turn immediately lead to factorizations of n: n=gcd(a+b,n)×gcd(a-b,n). If done right, it is almost certain that at least one such factorization will be nontrivial.

The second step is identical to the case of the rational sieve, and is a straightforward linear algebra problem. The first step, however, is done in a different, more efficient way than the rational sieve, by utilizing number fields.

Details of method

Let n be the integer we want to factor. We pick an irreducible polynomial f with integer coefficients, and an integer m such that f(m)≡0 (mod n) (we will explain how they are chosen in the next section). Let α be a root of f; we can then form the ring Z [α]. There is a unique ring homomorphism φ from Z[α] to Z/nZ that maps α to m. For simplicity, we'll assume that Z[α] is a unique factorization domain; the algorithm can be modified to work when it isn't, but then there are some additional complications.

Next, we set up two parallel factor bases, one in Z[α] and one in Z. The one in Z[α] consists of all the prime ideals in Z[α] whose norm is bounded by a chosen value $N_{\max }$ . The factor base in Z, as in the rational sieve case, consists of all prime integers up to some other bound.

We then search for relatively prime pairs of integers (a,b) such that:

a+bm is smooth with respect to the factor base in Z (i.e., it is a product of elements in the factor base).
a+bα is smooth with respect to the factor base in Z[α]; given how we chose the factor base, this is equivalent to the norm of a+bα being divisible only by primes less than $N_{\max }$ .

These pairs are found through a sieving process, analogous to the Sieve of Eratosthenes; this motivates the name "Number Field Sieve".

For each such pair, we can apply the ring homomorphism φ to the factorization of a+bα, and we can apply the canonical ring homomorphism from Z to Z/nZ to the factorization of a+bm. Setting these equal gives a multiplicative relation among elements of a bigger factor base in Z/nZ, and if we find enough pairs we can proceed to combine the relations and factor n, as described above.

Choice of parameters

Not every number is an appropriate choice for the SNFS: one needs to know in advance a polynomial f of appropriate degree (the optimal degree is conjectured to be $\left(3{\frac {\log N}{\log \log N}}\right)^{\frac {1}{3}}$ , which is 4, 5, or 6 for the sizes of N currently feasible to factorise) with small coefficients, and a value x such that $f(x)\equiv 0{\pmod {N}}$ where N is the number to factorise. There is an extra condition: x must satisfy $ax+b\equiv 0{\pmod {N}}$ for a and b no bigger than $N^{1/d}$ .

One set of numbers for which such polynomials exist are the $a^{b}\pm 1$ numbers from the Cunningham tables; for example, when NFSNET factored $3^{479}+1$ , they used the polynomial $x^{6}+3$ with $x=3^{80}$ , since $(3^{80})^{6}+3=3^{480}+3$ , and $3^{480}+3\equiv 0{\pmod {3^{479}+1}}$ .

Numbers defined by linear recurrences, such as the Fibonacci and Lucas numbers, also have SNFS polynomials, but these are a little more difficult to construct. For example, $F_{709}$ has polynomial $n^{5}+10n^{3}+10n^{2}+10n+3$ , and the value of x satisfies $F_{142}x-F_{141}=0$ .^[2]

If one already knows some factors of a large number compatible with SNFS, then one could do the SNFS calculation modulo the remaining part; for the NFSNET example above, $3^{479}+1=(2^{2}\times 158071\times 7167757\times 7759574882776161031)$ times a 197-digit composite number (the small factors were found by ECM), and the SNFS was performed modulo the 197-digit number. The number of relations required by SNFS still depends on the size of the large number, but the individual calculations are quicker modulo the smaller number.

Limitations of algorithm

This algorithm, as mentioned above, is very efficient for numbers of the form r^e±s, for r and s relatively small. It is also efficient for any integers which can be represented as a polynomial with small coefficients. This includes integers of the more general form ar^e±bs^f, and also for many integers whose binary representation has low Hamming weight. The reason for this is as follows: The Number Field Sieve performs sieving in two different fields. The first field is usually the rationals. The second is a higher degree field. The efficiency of the algorithm strongly depends on the norms of certain elements in these fields. When an integer can be represented as a polynomial with small coefficients, the norms that arise are much smaller than those that arise when an integer is represented by a general polynomial. The reason is that a general polynomial will have much larger coefficients, and the norms will be correspondingly larger. The algorithm attempts to factor these norms over a fixed set of prime numbers. When the norms are smaller, these numbers are more likely to factor.

Related Research Articles

In number theory, integer factorization is the decomposition of a positive integer into a product of integers. Every positive integer greater than 1 is either the product of two or more integer factors, in which case it is called a composite number, or it is not, in which case it is called a prime number. For example, $15$ is a composite number because $15 = 3 \cdot 5$ , but $7$ is a prime number because it cannot be decomposed in this way. If one of the factors is composite, it can in turn be written as a product of smaller factors, for example $60 = 3 \cdot 20 = 3 \cdot (5 \cdot 4)$ . Continuing this process until every factor is prime is called prime factorization; the result is always unique up to the order of the factors by the prime factorization theorem.

<span class="mw-page-title-main">Factorization</span> (Mathematical) decomposition into a product

In mathematics, factorization (or factorisation, see English spelling differences) or factoring consists of writing a number or another mathematical object as a product of several factors, usually smaller or simpler objects of the same kind. For example, $3 \times 5$ is an integer factorization of $15$ , and $(x - 2)(x + 2)$ is a polynomial factorization of $x 2 - 4$ .

In algebraic number theory, an algebraic integer is a complex number that is integral over the integers. That is, an algebraic integer is a complex root of some monic polynomial whose coefficients are integers. The set of all algebraic integers $A$ is closed under addition, subtraction and multiplication and therefore is a commutative subring of the complex numbers.

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 $⌊log 2 n ⌋ + 1$ bits) is of the form

The Lenstra elliptic-curve factorization or the elliptic-curve factorization method (ECM) is a fast, sub-exponential running time, algorithm for integer factorization, which employs elliptic curves. For general-purpose factoring, ECM is the third-fastest known factoring method. The second-fastest is the multiple polynomial quadratic sieve, and the fastest is the general number field sieve. The Lenstra elliptic-curve factorization is named after Hendrik Lenstra.

In mathematics, an irreducible polynomial is, roughly speaking, a polynomial that cannot be factored into the product of two non-constant polynomials. The property of irreducibility depends on the nature of the coefficients that are accepted for the possible factors, that is, the field to which the coefficients of the polynomial and its possible factors are supposed to belong. For example, the polynomial $x 2 - 2$ is a polynomial with integer coefficients, but, as every integer is also a real number, it is also a polynomial with real coefficients. It is irreducible if it is considered as a polynomial with integer coefficients, but it factors as $if it is considered as a polynomial with real coefficients. One says that the polynomial x 2 - 2 is irreducible over the integers but not over the reals.$

In mathematics, a reciprocity law is a generalization of the law of quadratic reciprocity to arbitrary monic irreducible polynomials $with integer coefficients. Recall that first reciprocity law, quadratic reciprocity, determines when an irreducible polynomial splits into linear terms when reduced mod . That is, it determines for which prime numbers the relation$

In mathematics, especially in the field of algebra, a polynomial ring or polynomial algebra is a ring formed from the set of polynomials in one or more indeterminates with coefficients in another ring, often a field.

In mathematics, Eisenstein's criterion gives a sufficient condition for a polynomial with integer coefficients to be irreducible over the rational numbers – that is, for it to not be factorizable into the product of non-constant polynomials with rational coefficients.

In mathematics, the ring of integers of an algebraic number field $is the ring of all algebraic integers contained in . An algebraic integer is a root of a monic polynomial with integer coefficients: . This ring is often denoted by or . Since any integer belongs to and is an integral element of, the ring is always a subring of .$

Chebotarev's density theorem in algebraic number theory describes statistically the splitting of primes in a given Galois extension K of the field $of rational numbers. Generally speaking, a prime integer will factor into several ideal primes in the ring of algebraic integers of K . There are only finitely many patterns of splitting that may occur. Although the full description of the splitting of every prime p in a general Galois extension is a major unsolved problem, the Chebotarev density theorem says that the frequency of the occurrence of a given pattern, for all primes p less than a large integer N, tends to a certain limit as N goes to infinity. It was proved by Nikolai Chebotaryov in his thesis in 1922, published in.$

The quadratic sieve algorithm (QS) is an integer factorization algorithm and, in practice, the second-fastest method known. It is still the fastest for integers under 100 decimal digits or so, and is considerably simpler than the number field sieve. It is a general-purpose factorization algorithm, meaning that its running time depends solely on the size of the integer to be factored, and not on special structure or properties. It was invented by Carl Pomerance in 1981 as an improvement to Schroeppel's linear sieve.

In mathematics, Hensel's lemma, also known as Hensel's lifting lemma, named after Kurt Hensel, is a result in modular arithmetic, stating that if a univariate polynomial has a simple root modulo a prime number $p$ , then this root can be lifted to a unique root modulo any higher power of $p$ . More generally, if a polynomial factors modulo $p$ into two coprime polynomials, this factorization can be lifted to a factorization modulo any higher power of $p$ .

In mathematics, the resultant of two polynomials is a polynomial expression of their coefficients that is equal to zero if and only if the polynomials have a common root, or, equivalently, a common factor. In some older texts, the resultant is also called the eliminant.

In algebra, Gauss's lemma, named after Carl Friedrich Gauss, is a statement about polynomials over the integers, or, more generally, over a unique factorization domain. Gauss's lemma underlies all the theory of factorization and greatest common divisors of such polynomials.

In mathematics, the rational sieve is a general algorithm for factoring integers into prime factors. It is a special case of the general number field sieve. While it is less efficient than the general algorithm, it is conceptually simpler. It serves as a helpful first step in understanding how the general number field sieve works.

In mathematics and computer algebra, factorization of polynomials or polynomial factorization expresses a polynomial with coefficients in a given field or in the integers as the product of irreducible factors with coefficients in the same domain. Polynomial factorization is one of the fundamental components of computer algebra systems.

Arjen Klaas Lenstra is a Dutch mathematician, cryptographer and computational number theorist. He is a professor emeritus from the École Polytechnique Fédérale de Lausanne (EPFL) where he headed of the Laboratory for Cryptologic Algorithms.

In algebra, the greatest common divisor of two polynomials is a polynomial, of the highest possible degree, that is a factor of both the two original polynomials. This concept is analogous to the greatest common divisor of two integers.

In mathematics and computer algebra the factorization of a polynomial consists of decomposing it into a product of irreducible factors. This decomposition is theoretically possible and is unique for polynomials with coefficients in any field, but rather strong restrictions on the field of the coefficients are needed to allow the computation of the factorization by means of an algorithm. In practice, algorithms have been designed only for polynomials with coefficients in a finite field, in the field of rationals or in a finitely generated field extension of one of them.

References

↑ Pomerance, Carl (December 1996), "A Tale of Two Sieves" (PDF), Notices of the AMS, vol. 43, no. 12, pp. 1473–1485
↑ Franke, Jens. "Installation notes for ggnfs-lasieve4". MIT Massachusetts Institute of Technology.

v t e Number-theoretic algorithms
Primality tests	AKS APR Baillie–PSW Elliptic curve Pocklington Fermat Lucas Lucas–Lehmer Lucas–Lehmer–Riesel Proth's theorem Pépin's Quadratic Frobenius Solovay–Strassen Miller–Rabin
Prime-generating	Sieve of Atkin Sieve of Eratosthenes Sieve of Pritchard Sieve of Sundaram Wheel factorization
Integer factorization	Continued fraction (CFRAC) Dixon's Lenstra elliptic curve (ECM) Euler's Pollard's rho p − 1 p + 1 Quadratic sieve (QS) General number field sieve (GNFS) Special number field sieve (SNFS) Rational sieve Fermat's Shanks's square forms Trial division Shor's
Multiplication	Ancient Egyptian Long Karatsuba Toom–Cook Schönhage–Strassen Fürer's
Euclidean division	Binary Chunking Fourier Goldschmidt Newton-Raphson Long Short SRT
Discrete logarithm	Baby-step giant-step Pollard rho Pollard kangaroo Pohlig–Hellman Index calculus Function field sieve
Greatest common divisor	Binary Euclidean Extended Euclidean Lehmer's
Modular square root	Cipolla Pocklington's Tonelli–Shanks Berlekamp Kunerth
Other algorithms	Chakravala Cornacchia Exponentiation by squaring Integer square root Integer relation (LLL; KZ) Modular exponentiation Montgomery reduction Schoof Trachtenberg system
Italics indicate that algorithm is for numbers of special forms