Special number field sieve

Special number field sieve

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 "r""e" ± "s", where "r" and "s" are small (for instance Mersenne numbers).

Heuristically, its complexity for factoring an integer n is of the form [Citation|last=Pomerance|first=Carl|author-link=Carl Pomerance|date=December 1996|title=A Tale of Two Sieves|periodical=Notices of the AMS|volume=43|issue=12|pages=1473-1485|url=http://www.ams.org/notices/199612/pomerance.pdf] :

:e^{left(1+o(1) ight)left(frac{32}{9}log n ight)^{frac{1}{3left(loglog n ight)^{frac{2}{3}=L_nleft [1/3,(32/9)^{1/3} ight] .

(in O and L notations).

The SNFS has been used extensively by NFSNet (a volunteer distributed computing effort) and others to factorise numbers of the Cunningham project; for some time the records for integer factorisation have been numbers factored by SNFS.

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/"n"Z, 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"2≡"b"2 (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: you need 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} ight) ^{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 is definitely divisible by 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. [cite web
last = Franke
first = Jens
title = Installation notes for ggnfs-lasieve4
url=http://stuff.mit.edu/afs/sipb/project/pari-gp/ggnfs/Linux/src/lasieve4/INSTALL.and.USE
publisher =MIT Massachusetts Institute of Technology
]

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 "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 "a'r""e"±"b's""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 thenorms are smaller, these numbers are more likely to factor.

References

External links

* http://www.nfsnet.org/

*

*cite web|author=A. K. Lenstra, H. W. Lenstra, Jr., M. S. Manasse, and J. M. Pollard|title=The Factorization of the Ninth Fermat Number|work=Math. Comp. 61|year=1993|pages=319-349|url=http://www.std.org/~msm/common/f9paper.ps|format=ps

*cite book|editor=A. K. Lenstra, H. W. Lenstra, Jr.|chapter=The Development of the Number Field Sieve|title=Lecture Notes in Mathematics|series=1554|publisher=Springer-Verlag|location=New York|year=1993|id=ISBN 978-3-540-57013-4


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • General number field sieve — In number theory, the general number field sieve (GNFS) is the most efficient classical algorithm known for factoring integers larger than 100 digits. Heuristically, its complexity for factoring an integer n (consisting of log2 n bits) is of …   Wikipedia

  • Number Field Sieve — Algorithme de factorisation par crible sur les corps de nombres généralisé En mathématiques, le crible général de corps de nombres est l algorithme, fondé sur l arithmétique modulaire, pour la décomposition en produit de facteurs premiers le plus …   Wikipédia en Français

  • Sieve of Eratosthenes — Sieve of Eratosthenes: algorithm steps for primes below 121 (including optimization of starting from prime s square). In mathematics, the sieve of Eratosthenes (Greek: κόσκινον Ἐρατοσθένους), one of a number of prime number sieves, is a simple,… …   Wikipedia

  • List of number theory topics — This is a list of number theory topics, by Wikipedia page. See also List of recreational number theory topics Topics in cryptography Contents 1 Factors 2 Fractions 3 Modular arithmetic …   Wikipedia

  • Fibonacci number — A tiling with squares whose sides are successive Fibonacci numbers in length …   Wikipedia

  • Number theory — A Lehmer sieve an analog computer once used for finding primes and solving simple diophantine equations. Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers (the… …   Wikipedia

  • Prime number — Prime redirects here. For other uses, see Prime (disambiguation). A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is… …   Wikipedia

  • Quadratic sieve — The quadratic sieve algorithm (QS) is a modern integer factorization algorithm and, in practice, the second fastest method known (after the general number field sieve). It is still the fastest for integers under 100 decimal digits or so, and is… …   Wikipedia

  • 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… …   Wikipedia

  • Number — For other uses, see Numbers (disambiguation). A number is a mathematical object used to count and measure. In mathematics, the definition of number has been extended over the years to include such numbers as zero, negative numbers, rational… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”