Special Method for Sieve a Number Field

The special method of sifting a number field ( English special number filter sieve , SNFS) is a method of factoring integers of a special kind. From it, a general method for sifting a number field was obtained, which is the most effective algorithm for factoring large integers $n>10^{110}$ ${\ displaystyle n> 10 ^ {110}}$ $n> 10 ^ {{110}}$ . The method is effective for integers of the form r ^e ± s , where r $\in$ ${\ displaystyle \ in}$ $\ in$ N s $\in$ ${\ displaystyle \ in}$ $\ in$ Z, r, and s are small (e.g., the Mersenne Numbers ).

A heuristic estimate of the complexity of factorization of the number n is expressed by the formula ^[1] :

e^{\left(1+o(1)\right)\left({\frac {32}{9}}\log n\right)^{\frac {1}{3}}\left(\log \log n\right)^{\frac {2}{3}}}=L_{n}\left[1/3,(32/9)^{1/3}\right]

{\ displaystyle e ^ {\ left (1 + o (1) \ right) \ left ({\ frac {32} {9}} \ log n \ right) ^ {\ frac {1} {3}} \ left (\ log \ log n \ right) ^ {\ frac {2} {3}}} = L_ {n} \ left [1/3, (32/9) ^ {1/3} \ right]}

{\ displaystyle e ^ {\ left (1 + o (1) \ right) \ left ({\ frac {32} {9}} \ log n \ right) ^ {\ frac {1} {3}} \ left (\ log \ log n \ right) ^ {\ frac {2} {3}}} = L_ {n} \ left [1/3, (32/9) ^ {1/3} \ right]}

Using SNFS, the Fermat Number was Factored $F_{9}=2^{512}+1$ ${\ displaystyle F_ {9} = 2 ^ {512} +1}$ ${\ displaystyle F_ {9} = 2 ^ {512} +1}$ containing 155 decimal digits ^[2] .

History

The main idea of the method was first proposed by John Pollard in his article ^[3] , which he sent out to his colleagues in 1988. In it, he illustrated his method on the seventh number of Fermat $2^{128}+1$ ${\ displaystyle 2 ^ {128} +1}$ $2^{128}+1$ . The idea was to perform screening not in a ring of integers, as in the quadratic sieve method, but in an algebraic number field. In 1990, the ninth number of Fermat was decomposed using this method. $F_{9}=2^{512}+1$ ${\ displaystyle F_ {9} = 2 ^ {512} +1}$ $F_{9}=2^{512}+1$ . Initially, the method was applicable only for numbers of a special type 2 ⁿ ± c , therefore it was called "a special method for sifting a number field." Later, the method was modified for arbitrary numbers and called the general method of numerical sieve .

Method Overview

SNFS is based on a simpler rational sieve method. The reader is invited to familiarize themselves with this method before studying SNFS.

SNFS works as follows. Let n be the number to factorize. Similar to the rational sieve method, the SNFS algorithm can be divided into two steps:

Finding the number of multiplicative ratios of the factor base Z / n Z greater than the number of elements in the factor base.
Multiplication of relations among themselves so that the degrees of the resulting products are the same, that is, obtaining relations of the form a ² ≡ b ² ( mod n ). This in turn will lead to factorization of n : n = GCD ( a + b , n ) × GCD ( a - b , n ). If the obtained decomposition is trivial (i.e., n = n × 1), one should look for other products of relations satisfying this condition.

The second step is identical to the step in the rational sieve method and is the task of linear algebra. Unlike the first step, which in this method is more effective.

Method Details

Let n be a factorizable number. Take an irreducible polynomial f and an integer m such that f ( m ) ≡0 ( mod n ) (the principles of their choice will be explained in the next section). Let α be the root of f ; then there exists a ring Z [α]. Then there exists a unique homomorphism ring φ between Z [ α ] and Z / n Z that maps α to m . For simplicity, we assume that Z [ α ] is a factorial ring ; the method can be modified for the case when this condition is not fulfilled, which will lead to additional calculations.

Then we create two factor bases , one for Z [ α ] and one for Z. The factor base Z [ α ] contains all the prime numbers Z [ α ] whose size is limited by the value $N_{\max }$ ${\ displaystyle N _ {\ max}}$ . The factor base Z , as in the rational sieve method, consists of primes up to a certain boundary number.

Then we look for mutually prime numbers ( a , b ) such that:

a + bm is smooth with respect to the elements of the factor base Z (that is, all its prime divisors are contained in the factor base).
a + bα is smooth with respect to the elements of the factor base Z [ α ]; from the way we choose the elements of the factor base, this condition is equivalent to the fact that a + bα is divisible only by primes smaller $N_{\max }$ ${\ displaystyle N _ {\ max}}$ .

These pairs of numbers are found by a sieving method similar to the sieve method of Eratosthenes ; this explains the name of the number field sieve method.

For each such pair of numbers ( a , b ), we can apply the homomorphism ring φ to factorize a + bα and the canonical homomorphism ring from Z to Z / n Z to factorize a + bm . Equating them, we obtain multiplicative relations for the elements of the factor base Z / n Z. Having found a sufficient number of such ratios, we multiply them among themselves as described above.

Select options

Not every number is suitable for SNFS factorization: it is necessary to find a polynomial f of suitable degree in advance (the optimal degree is assumed to be $\left(3{\frac {\log N}{\log \log N}}\right)^{1/3}$ ${\ displaystyle \ left (3 {\ frac {\ log N} {\ log \ log N}} \ right) ^ {1/3}}$ ; for the moment numbers N factorized at the moment, it is 4.5 or 6) with small coefficients and x such that $f(x)\equiv 0{\pmod {N}}$ ${\ displaystyle f (x) \ equiv 0 {\ pmod {N}}}$ where N is the number to factorize. Also x must be such that $ax+b\equiv 0{\pmod {N}}$ ${\ displaystyle ax + b \ equiv 0 {\ pmod {N}}}$ for a and b not large $N^{1/d}$ ${\ displaystyle N ^ {1 / d}}$ .

One of the types of numbers for which such polynomials exist are numbers of the form $a^{b}\pm 1$ ${\ displaystyle a ^ {b} \ pm 1}$ ; for example, when NFSNET expanded the number 3 ^ 479 + 1, they used the polynomial x ^ 6 + 3 for x = 3 ^ 80, since (3 ^ 80) ^ 6 + 3 = 3 ^ 480 + 3 and $3^{480}+3\equiv 0{\pmod {3^{479}+1}}$ ${\ displaystyle 3 ^ {480} +3 \ equiv 0 {\ pmod {3 ^ {479} +1}}}$ .

Numbers defined by linear recurrence relations, such as Fibonacci numbers and Luke numbers , also have SNFS polynomials, but they are a little more difficult to obtain. For example, $F_{709}$ ${\ displaystyle F_ {709}}$ has a polynomial $n^{5}+10n^{3}+10n^{2}+10n+3$ ${\ displaystyle n ^ {5} + 10n ^ {3} + 10n ^ {2} + 10n + 3}$ , and a value of x satisfying $F_{142}x-F_{141}=0$ ${\ displaystyle F_ {142} x-F_ {141} = 0}$ . ^[four]

If you know some divisors of a large SNFS number, you can perform SNFS calculations for the rest; for the example above from NFSNET, 3 ^ 479 + 1 = (4 · 158071 · 7167757 · 7759574882776161031) times the 197-digit compound number (small dividers were excluded by ECM ), and SNFS was used for the 197-digit number. The number of operations for NFS depends on the size of the original number, but some calculations are faster modulo a smaller number.

Limitations

This method, as noted above, is very effective for numbers of the form r ^e ± s , where r and s are relatively small. It is also effective for numbers that can be represented as polynomials with small coefficients. The fact is that a special method of sieving a number field performs sifting for two number fields. The effectiveness of the method greatly depends on the size of certain elements in these fields. If a number can be represented in the form of a polynomial with small coefficients, the numbers with which the calculations are performed are much smaller than the numbers that have to be dealt with if such a polynomial does not exist.

Notes

↑ Pomerance, Carl (December 1996), " A Tale of Two Sieves ", Notices of the AMS T. 43 (12): 1473-1485 , < http://www.ams.org/notices/199612/pomerance.pdf >
↑ Vasilenko, O.N. (2003), Number-theoretic algorithms of cryptography , p. 93-107 , < http://www.ict.edu.ru/ft/002416/book.pdf >
↑ Pollard, JM (1988), Factoring with cubic numbers
↑ Franke, Jens Installation notes for ggnfs-lasieve4 (neopr.) . MIT Massachusetts Institute of Technology. Archived on September 5, 2012.

Literature

Ishmukhametov, Sh.T. (2011), Methods of factorization of natural numbers , p. 145-175 , < http://window.edu.ru/window_catalog/files/r73980/Monograph_ishm.pdf > (inaccessible link)
Byrnes, Steven (May 18, 2005), " The Number Field Sieve ", Math 129 , < http://modular.fas.harvard.edu/129-05/final_papers/Steve_Byrnes.pdf > . Retrieved December 4, 2011. Archived September 20, 2006 on the Wayback Machine
Lenstra, AK ; Lenstra, HW, Jr. ; Manasse, MS & Pollard, JM (1993), " The Factorization of the Ninth Fermat Number ", Mathematics of Computation T. 61 (203): 319–349, doi : 10.1090 / S0025-5718-1993-1182953-4 , < http://www.std.org/~msm/common/f9paper.ps >
Lenstra, AK & Lenstra, HW, Jr., eds. (1993), The Development of the Number Field Sieve , vol. 1554, Lecture Notes in Mathematics, New York: Springer-Verlag, ISBN 3540570136
Silverman, Robert D. (2007), "Optimal Parameterization of SNFS", J. Mathematical Cryptology (de Gruyter). - T. 1: 105–124

Links

NFS @ Home

[1] Pomerance, Carl (December 1996), " A Tale of Two Sieves ", Notices of the AMS T. 43 (12): 1473-1485 , < http://www.ams.org/notices/199612/pomerance.pdf >

[2] Vasilenko, O.N. (2003), Number-theoretic algorithms of cryptography , p. 93-107 , < http://www.ict.edu.ru/ft/002416/book.pdf >

[3] Pollard, JM (1988), Factoring with cubic numbers

[4] Franke, Jens Installation notes for ggnfs-lasieve4 (neopr.) . MIT Massachusetts Institute of Technology. Archived on September 5, 2012.