Special number field sieve
Encyclopedia
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.
The special number field sieve is efficient for integers of the form re ± s, where r and s are small (for instance Mersenne numbers).
Heuristic
ally, its complexity
for factoring an integer
is of the form:
in O
and L-notation
s.
The SNFS has been used extensively by NFSNet (a volunteer distributed computing
effort), NFS@Home and others to factorise numbers of the Cunningham project
; for some time the records for integer factorisation
have been numbers factored by SNFS.
; 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:
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
.
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
. 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:
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.
, which is 4, 5, or 6 for the sizes of N currently feasible to factorise) with small coefficients, and a value x such that 
where N is the number to factorise. There is an extra condition: x must satisfy 
for a and b no bigger than 
.
One set of numbers for which such polynomials exist are the
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
.
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,
has polynomial 
, and the value of x satisfies 
.
If you already know some factors of a large SNFS-number, you can do the SNFS calculation modulo the remaining part; for the NFSNET example above, 3^479+1 = (4*158071*7167757*7759574882776161031) times a 197-digit composite number (the small factors were removed 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.
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.
Number theory
Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...
, a branch of mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, the special number field sieve (SNFS) is a special-purpose integer factorization
Integer factorization
In number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer....
algorithm. The general number field sieve
General number field sieve
In number theory, the general number field sieve is the most efficient classical algorithm known for factoring integers larger than 100 digits...
(GNFS) was derived from it.
The special number field sieve is efficient for integers of the form re ± s, where r and s are small (for instance Mersenne numbers).
Heuristic
Heuristic
Heuristic refers to experience-based techniques for problem solving, learning, and discovery. Heuristic methods are used to speed up the process of finding a satisfactory solution, where an exhaustive search is impractical...
ally, its complexity
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
for factoring an integer
is of the form:in O
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
and L-notation
L-notation
L-notation is an asymptotic notation analogous to big-O notation, denoted as L_n[\alpha,c] for a bound variable n tending to infinity. Like big-O notation, it is usually used to roughly convey the computational complexity of a particular algorithm....
s.
The SNFS has been used extensively by NFSNet (a volunteer distributed computing
Distributed computing
Distributed computing is a field of computer science that studies distributed systems. A distributed system consists of multiple autonomous computers that communicate through a computer network. The computers interact with each other in order to achieve a common goal...
effort), NFS@Home and others to factorise numbers of the Cunningham project
Cunningham project
The Cunningham project aims to find factors of large numbers of the formb^n \pm 1for b = 2, 3, 5, 6, 7, 10, 11, 12 and large exponents n. The project is named after Allan Joseph Champneys Cunningham, who published the first version of the table together with Herbert J. Woodall in 1925...
; for some time the records for integer factorisation
Integer factorization records
Integer factorization is the process of determining which prime numbers divide a given positive integer. Doing this quickly has applications in cryptography...
have been numbers factored by SNFS.
Overview of method
The SNFS is based on an idea similar to the much simpler rational sieveRational sieve
In mathematics, the rational sieve is a general algorithm for factoring integers into prime factors. It is essentially a special case of the general number field sieve, and while it is far less efficient than the general algorithm, it is conceptually far simpler...
; in particular, readers may find it helpful to read about the rational sieve
Rational sieve
In mathematics, the rational sieve is a general algorithm for factoring integers into prime factors. It is essentially a special case of the general number field sieve, and while it is far less efficient than the general algorithm, it is conceptually far simpler...
first, before tackling the SNFS.
The SNFS works as follows. Let n be the integer we want to factor. As in the rational sieve
Rational sieve
In mathematics, the rational sieve is a general algorithm for factoring integers into prime factors. It is essentially a special case of the general number field sieve, and while it is far less efficient than the general algorithm, it is conceptually far simpler...
, 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 a2≡b2 (modModular arithmeticIn mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value—the modulus....
n). These in turn immediately lead to factorizations of n: n=gcdGreatest common divisorIn mathematics, the greatest common divisor , also known as the greatest common factor , or highest common factor , of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.For example, the GCD of 8 and 12 is 4.This notion can be extended to...
(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
Rational sieve
In mathematics, the rational sieve is a general algorithm for factoring integers into prime factors. It is essentially a special case of the general number field sieve, and while it is far less efficient than the general algorithm, it is conceptually far simpler...
, and is a straightforward linear algebra
Linear algebra
Linear algebra is a branch of mathematics that studies vector spaces, also called linear spaces, along with linear functions that input one vector and output another. Such functions are called linear maps and can be represented by matrices if a basis is given. Thus matrix theory is often...
problem. The first step, however, is done in a different, more efficient
Algorithmic efficiency
In computer science, efficiency is used to describe properties of an algorithm relating to how much of various types of resources it consumes. Algorithmic efficiency can be thought of as analogous to engineering productivity for a repeating or continuous process, where the goal is to reduce...
way than the rational sieve, by utilizing number fields
Algebraic number field
In mathematics, an algebraic number field F is a finite field extension of the field of rational numbers Q...
.
Details of method
Let n be the integer we want to factor. We pick an irreducible polynomialIrreducible polynomial
In mathematics, the adjective irreducible means that an object cannot be expressed as the product of two or more non-trivial factors in a given set. See also factorization....
f with integer coefficients, and an integer m such that f(m)≡0 (mod
Modular arithmetic
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value—the modulus....
n) (we will explain how they are chosen in the next section). Let α be a root of f; we can then form the ring
Ring (mathematics)
In mathematics, a ring is an algebraic structure consisting of a set together with two binary operations usually called addition and multiplication, where the set is an abelian group under addition and a semigroup under multiplication such that multiplication distributes over addition...
Z
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
[α]. There is a unique ring homomorphism
Ring homomorphism
In ring theory or abstract algebra, a ring homomorphism is a function between two rings which respects the operations of addition and multiplication....
φ from Z[α] to Z/nZ that maps α to m. For simplicity, we'll assume that Z[α] is a unique factorization domain
Unique factorization domain
In mathematics, a unique factorization domain is, roughly speaking, a commutative ring in which every element, with special exceptions, can be uniquely written as a product of prime elements , analogous to the fundamental theorem of arithmetic for the integers...
; 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
. 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 smoothSmooth numberIn number theory, a smooth number is an integer which factors completely into small prime numbers. The term seems to have been coined by Leonard Adleman. Smooth numbers are especially important in cryptography relying on factorization.-Definition:...
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
.
These pairs are found through a sieving process, analogous to the Sieve of Eratosthenes
Sieve of Eratosthenes
In mathematics, the sieve of Eratosthenes , one of a number of prime number sieves, is a simple, ancient algorithm for finding all prime numbers up to a specified integer....
; 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: you need to know in advance a polynomial f of appropriate degree (the optimal degree is conjectured to be, which is 4, 5, or 6 for the sizes of N currently feasible to factorise) with small coefficients, and a value x such that where N is the number to factorise. There is an extra condition: x must satisfy for a and b no bigger than .One set of numbers for which such polynomials exist are the
numbers from the Cunningham tablesCunningham project
The Cunningham project aims to find factors of large numbers of the formb^n \pm 1for b = 2, 3, 5, 6, 7, 10, 11, 12 and large exponents n. The project is named after Allan Joseph Champneys Cunningham, who published the first version of the table together with Herbert J. Woodall in 1925...
; 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
.Numbers defined by linear recurrences, such as the Fibonacci
Fibonacci number
In mathematics, the Fibonacci numbers are the numbers in the following integer sequence:0,\;1,\;1,\;2,\;3,\;5,\;8,\;13,\;21,\;34,\;55,\;89,\;144,\; \ldots\; ....
and Lucas
Lucas number
The Lucas numbers are an integer sequence named after the mathematician François Édouard Anatole Lucas , who studied both that sequence and the closely related Fibonacci numbers...
numbers, also have SNFS polynomials, but these are a little more difficult to construct. For example,
has polynomial , and the value of x satisfies .If you already know some factors of a large SNFS-number, you can do the SNFS calculation modulo the remaining part; for the NFSNET example above, 3^479+1 = (4*158071*7167757*7759574882776161031) times a 197-digit composite number (the small factors were removed 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 re±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 a're±b'sf, 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.