Law of demand

2014-01-17T17:46:01Z

49.249.130.152: /* Assumptions */

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 ''r''''e'' ± ''s'', where ''r'' and ''s'' are small (for instance [[Mersenne number]]s).

[[Heuristic]]ally, its [[Computational complexity theory|complexity]] for factoring an integer <math>n</math> is of the form:<ref>{{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}}</ref>

:<math>\exp\left(\left(1+o(1)\right)\left(\tfrac{32}{9}\log n\right)^{1/3}\left(\log\log n\right)^{2/3}\right)=L_n\left[1/3,(32/9)^{1/3}\right]</math>

in [[Big O notation|O]] and [[L-notation]]s.

The SNFS has been used extensively by NFSNet (a volunteer [[distributed computing]] effort), [http://escatter11.fullerton.edu/nfs/ NFS@Home] and others to factorise numbers of the [[Cunningham project]]; for some time the [[Integer factorization records|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 [[Modular arithmetic#Ring of congruence classes|'''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&equiv;''b''2 ([[modular arithmetic|mod]] ''n''). These in turn immediately lead to factorizations of ''n'': ''n''=[[greatest common divisor|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 [[algorithmic efficiency|efficient]] way than the rational sieve, by utilizing [[algebraic number field|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'')&equiv;0 ([[modular arithmetic|mod]] ''n'') (we will explain how they are chosen in the next section). Let ''α'' be a [[Root of a function|root]] of ''f''; we can then form the [[ring (mathematics)|ring]] '''[[integer|Z]]'''[α]. There is a unique [[ring homomorphism]] φ from '''Z'''[''α''] to [[Modular arithmetic#Ring of congruence classes|'''Z'''/n'''Z''']] 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 <math>N_{\max}</math>. 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 number|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 <math>N_{\max}</math>.

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'''/n'''Z''' to the factorization of ''a''+''bm''. Setting these equal gives a multiplicative relation among elements of a bigger factor base in '''Z'''/n'''Z''', 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 <math>\left(3 \frac{\log N}{\log \log N}\right) ^{1/3}</math>, which is 4, 5, or 6 for the sizes of N currently feasible to factorise) with small coefficients, and a value ''x'' such that <math>f(x) \equiv 0 \pmod N</math> where N is the number to factorise. There is an extra condition: ''x'' must satisfy <math>ax+b \equiv 0 \pmod N</math> for a and b no bigger than <math>N^{1/d}</math>.

One set of numbers for which such polynomials exist are the <math>a^b \pm 1</math> numbers from the [[Cunningham project|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 <math>3^{480}+3 \equiv 0 \pmod {3^{479}+1}</math>.

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

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 [[elliptic curve method|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 the
norms are smaller, these numbers are more likely to factor.

== See also ==
* [[General number field sieve]]

== References ==
{{reflist}}

==Further reading==
*{{Citation |last=Byrnes |first=Steven |lastauthoramp= |date=May 18, 2005 |title=The Number Field Sieve |journal=Math 129 |volume= |issue= |pages= |url=http://modular.fas.harvard.edu/129-05/final_papers/Steve_Byrnes.pdf |issn= }}
*{{Citation |doi=10.1090/S0025-5718-1993-1182953-4 |last=Lenstra |first=A. K. |authorlink=Arjen Lenstra |last2=Lenstra |first2=H. W., Jr. |authorlink2=Hendrik Lenstra |last3=Manasse |first3=M. S. |last4=Pollard |first4=J. M. |lastauthoramp=yes |year=1993 |title=The Factorization of the Ninth Fermat Number |journal=Mathematics of Computation |volume=61 |issue=203 |pages=319–349 |url=http://www.std.org/~msm/common/f9paper.ps |issn= }}
*{{citation |editor-last=Lenstra |editor-first=A. K. |editor2-last=Lenstra |editor2-first=H. W., Jr. |title=The Development of the Number Field Sieve |series=Lecture Notes in Mathematics |volume=1554 |year=1993 |publisher=Springer-Verlag |location=New York |isbn=3-540-57013-6 |pages= |url= }}
*{{citation |last=Silverman |first=Robert D. |title=Optimal Parameterization of SNFS |journal=J. Mathematical Cryptology |volume=1 |year=2007 |publisher=de Gruyter |pages= 105–124 |doi=10.1515/JMC.2007.007}}

==External links==
* http://www.nfsnet.org/

{{number theoretic algorithms}}

[[Category:Integer factorization algorithms]]

formulasearchengine - User contributions [en]

Law of demand