2
$\begingroup$

The special number field sieve (SNFS) is an algorithm to calculate discrete logarithms and to factor numbers, given that the target has a special structure.

Now, all ressources always say something like

The special number field sieve is efficient for integers of the form $r^e \pm s$, where $r$ and $s$ are small

So my question is:
How can "small" be quantified in this context?

Is an integer small if it is small than $2^{10}$ or rather $2^{40}$? Is there even a hard boundary or a heuristic boundary? Is there a way to estimate the (asymptotic) running-time which also uses these "small" values?

$\endgroup$
  • $\begingroup$ It is faster to work with polynomials that have smaller (integer) coefficients. The context is "small enough" that choosing the polynomial pair using a somewhat "evident" or at least manually constructible approach is better than using the searched-for polynomial pair techniques of GNFS. An early account (R. M. Elkenbracht-Huizing, 1995) gives details, which I'll summarize below. $\endgroup$ – hardmath Nov 29 '17 at 14:05
2
$\begingroup$

We summarize the discussion of parameters to express numbers suitable to be factored::

$$ N = C_1 r^t + C_2 s^u $$

by the Special Number Field Sieve (SNFS) from the paper "An Implementation of the Number Field Sieve" by Marije Elkenbracht-Huizing (1996).

She describes the Number Field Sieve this way:

Let $n$ be the odd number to be factored. It is easy to check whether $n$ is a prime number or a prime power ,and we assume that it is neither. Like [Multiple Polynomial Quadratic Sieve], the NFS tries to fi nd a solution of the equation $v^2=w^2 \bmod{n}.$ For at least half of the pairs $(v \bmod n, w \bmod n)$ with $v^2\neq w^2 \bmod n$ and $v$ and $w$ relatively prime to $n$, the greatest common divisor of $n$ and $v-w$ gives a nontrivial factor of $n$.

To construct $v$ and $w$ we first choose two polynomials $$ f_1(x) = c_{1,d_1}x^{d_1} + c_{1,d_1-1}x^{d_1-1} + \ldots + c_{1,0} $$ $$ f_2(x) = c_{2,d_2}x^{d_2} + c_{2,d_2-1}x^{d_2-1} + \ldots + c_{2,0} $$ over $\mathbb{Z}$, with $f_1 \neq \pm f_2$, both irreducible over $\mathbb{Z}$ and having content $\text{cont }f_i := \gcd(c_{i,d_i},\ldots,c_{i,0})$ equal to $1$; we also choose an integer $m$ that is a common root modulo $n$ of $f_1$ and $f_2$. In our implementation this is the only step in which the SNFS and the GNFS differ: in the SNFS we use the special form of $n$ to pick these polynomials by hand. One polynomial will have very small coefficients compared to the coefficients of the polynomials we will use with the GNFS, where we search for a pair of polynomials with help of the computer. This makes SNFS faster than GNFS.

Tying what makes "SNFS faster than GNFS" to a manual process of picking a pair of (integer) polynomials (so that "one polynomial will have very small coefficients" compared to the polynomials "where we search... with help of the computer") makes the distinction contingent on the (advancing) state of the art in computer search for polynomials. Potentially the algorithms for polynomial selection will improve so far as to practically erase the distinction.

Analysis of what effect small coefficients have on the algorithm (in particular on the speed of the sieving phase) is beyond the limits of the present post. However useful perspective comes from examining the cases set out by Elkenbracht-Huizing's paper. Here are simplified tables of various factoring successes listed there:

Table 1: SNFS Example Polynomials and Timings $$ \begin{array}{|l|c|c|c|} \hline n \text{ factor of } N & f_1(x) & f_2(x) & \begin{array}{c} \text{sieve} \\ \text{hours} \end{array} \\ \hline \begin{array}{c} \text{C98 from } \\ 7^{128} + 6^{128} \end{array} & x^4 + 1 & 6^{32}x - 7^{32} & 450 \\ \hline \begin{array}{c} \text{C106 from } \\ 2^{543} + 1 \end{array} & \begin{array}{c} 4x^4 \\+2x^2 + 1 \end{array} & x - 2^{90} & 250 \\ \hline \begin{array}{c} \text{C119 from } \\ 3^{319} - 1 \end{array} & \begin{array}{c} x^5 + x^4 \\ - 4x^3 -3x^2 \\+3x + 1\end{array} & \begin{array}{c} 3^{29}x \\- (3^{58} +1) \end{array} & 800 \\ \hline \begin{array}{c} \text{C123 from } \\ 2^{511} - 1 \end{array} & \begin{array}{c} x^6 -10x^4 \\+24x^2 -8\end{array} & \begin{array}{c} 2^{36}x \\- (2^{73} +1) \end{array} & 700 \\ \hline \begin{array}{c} \text{C135 from } \\ 73^{73} - 1 \end{array} & x^5 + 73^2 & x - 73^{15} & 2150 \\ \hline \begin{array}{c} \text{C165 from } \\ 12^{151} -1 \end{array} & 12x^5 - 1 & x - 12^{30} & \lt 1680 \\ \hline \end{array} $$

Table 2: GNFS Example Polynomials and Timings $$ \begin{array}{|l|c|c|c|} \hline n \text{ factor of } N & f_1(x) & f_2(x) & \begin{array}{c} \text{sieve} \\ \text{hours} \end{array} \\ \hline \begin{array}{c} \text{C87 from } \\ 72^{99} + 1 \end{array} & \begin{array}{c} 1.5E20x^2 \\ - 1.4E21x \\- 8.3E21 \end{array} & \begin{array}{c} 1.0E21x^2 \\ + 7.0E21x \\- 7.4E22\end{array} & 2100 \\ \hline \begin{array}{c} \text{C87 from } \\ 72^{99} + 1 \end{array} & \begin{array}{c} 7.3E8x^2 \\ + 2.0E20x \\- 7.8E33\end{array} & \begin{array}{c} 2.2E9x^2 \\ - 7.9E21x \\- 2.3E34\end{array} & 1500 \\ \hline \begin{array}{c} \text{C97 from } \\ 12^{441} + 1 \end{array} & \begin{array}{c} -3.0E10x^2 \\+ 4.4E23x \\+ 3.6E36 \end{array} & \begin{array}{c} -5.4E11x^2 \\ - 4.8E24x \\+ 6.3E37 \end{array} & 3500 \\ \hline \begin{array}{c} \text{C105 from } \\ 3^{367} - 1 \end{array} & \begin{array}{c} 3.4E11x^2 \\ + 8.7E25x \\+ 5.4E38\end{array} & \begin{array}{c} 1.2E12x^2 \\ - 9.1E26x \\+ 1.3E41 \end{array} & \lt 7680 \\ \hline \begin{array}{c} \text{C106 from } \\ 12^{157} + 1 \end{array} & \begin{array}{c} 1.9E11x^2 \\ - 1.0E26x \\- 3.2E40\end{array} & \begin{array}{c} -7.9E11x^2 \\ - 4.0E26x \\+ 1.6E41 \end{array} & 11900 \\ \hline \begin{array}{c} \text{C107 from } \\ 6^{223} + 1 \end{array} & \begin{array}{c} -5.4E11x^2 \\ - 4.3E26x \\- 4.7E40\end{array} & \begin{array}{c} -2.4E11x^2 \\ + 7.6E26x \\- 3.1E41 \end{array} & 11200 \\ \hline \end{array} $$

I'll append some additional remarks, but the first columns describe the number of digits of a composite factor of an expression, the second and third columns give the pair of polynomials used (in "scientific notation" for the large integer coefficients of the GNFS; see paper for exact values), and the last column gives a rough timing for the sieving (of relations) step.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.