SNFS polynomial selection

For the SNFS factorization you need two polynomials with small coefficients and a common root modulo N, the number to be factored. Typically one polynomial is of degree 4, 5 or 6 (the algebraic side) and the other one is linear (the rational side).

Cyclotomic numbers

For cyclotomic numbers, there are four standard operations you can perform on the number to derive suitable polynomials:

1. Multiplying by a constant
2. Increasing or decreasing a power
3. Dividing out algebraic factors
4. halving the degree of a symmetric polynomial

1. Suppose you want to factor a number of the form [math]\displaystyle{ a^{59}-1 }[/math] for a given a with a quintic (a degree 5 polynomial). You can multiply N by a and get [math]\displaystyle{ aN=a^{60}-a }[/math], which you can express as [math]\displaystyle{ x^5-a }[/math] with root [math]\displaystyle{ m=a^{12} }[/math]. For example, the smallest [math]\displaystyle{ a^{59}-1 }[/math] number currently not completely factored is [math]\displaystyle{ 208^{59}-1 }[/math], the polynomials would be [math]\displaystyle{ x^5-208 }[/math] on the algrebraic side and [math]\displaystyle{ x-6557827967253220516257857536 }[/math] on the rational side. Multiplying N by a constant increases the SNFS difficulty of the factorisation.

2. If you want to factor [math]\displaystyle{ a^{61}-1 }[/math], you can rewrite the power as [math]\displaystyle{ a\cdot a^{60} }[/math] and get [math]\displaystyle{ a\cdot a^{60}-1 }[/math], or [math]\displaystyle{ a x^5-1 }[/math], again with root [math]\displaystyle{ m=a^{12} }[/math]. Thus, your polynomials are, for example for [math]\displaystyle{ N=208^{61}-1 }[/math], [math]\displaystyle{ 208x^5-1 }[/math] and [math]\displaystyle{ x-6557827967253220516257857536 }[/math].

You can use both methods to get the exponent a multiple of the degree you want to use, choose the one that minimises the largest coefficient of the algebraic polynomial.

You can also combine both methods if the base is composite. If you want to factor, say, [math]\displaystyle{ 10^{113}-1 }[/math] with a quintic, you could use [math]\displaystyle{ 1000x^5-1 }[/math] (difficulty 113) or [math]\displaystyle{ x^5-100 }[/math] (difficulty 115) by the method of 1. or 2. alone.

But you can also first multiply N by [math]\displaystyle{ 5^2 }[/math] to get [math]\displaystyle{ 25N=2^{113} \cdot 5^{115} - 25 }[/math], then rewrite as [math]\displaystyle{ 8 (2^{110} 5^{115}) - 25 }[/math], or [math]\displaystyle{ 8x^5-25 }[/math], with root [math]\displaystyle{ m=2^{22} \cdot 5^{23} }[/math] (difficulty ~114). So your polynomials are [math]\displaystyle{ 8x^5-25 }[/math] and [math]\displaystyle{ x-50000000000000000000000 }[/math]. The advantage is that the largest coefficient in the algebraic poly is now only 25 instead of 100 and you still have a low difficulty.

3. If your exponent is divisible by 3, 5 or 7, you can divide out an algebraic factor and immediately get a polynomial of suitable degree and small coefficients.

• [math]\displaystyle{ (a^{3k}-1)/(a^k-1) = a^{2k} + a^k + 1 }[/math] which can be converted to a quadratic [math]\displaystyle{ x^2+x+1 }[/math] with root [math]\displaystyle{ a^k }[/math]. However, a quadratic has too small degree, the coefficients on the rational side would become huge. Instead, if k is odd, we write [math]\displaystyle{ a^2\cdot a^{2(k-1)} + a\cdot a^{k-1} + 1 }[/math] and can convert to a quartic in [math]\displaystyle{ a^{(k-1)/2} }[/math]. If you want a sextic, tweak the exponents accordingly by 2., perhaps multiplying by a power of a (as in 1.) to get small coefficients.
• [math]\displaystyle{ (a^{5k}-1)/(a^k-1) = a^{4k} + a^{3k} + a^{2k} + a^k + 1 }[/math], which is a useable quartic in [math]\displaystyle{ a^k }[/math].
• [math]\displaystyle{ (a^{7k}-1)/(a^k-1) = a^{6k} + a^{5k} + a^{4k} + a^{3k} + a^{2k} + a^k + 1 }[/math], which is a useable sextic in [math]\displaystyle{ a^k }[/math].

4. For [math]\displaystyle{ a^{11k}-1 }[/math] and [math]\displaystyle{ a^{13k}-1 }[/math] you'd get degrees 10 and 12, respectively - too large. But the resulting polynomial is symmetric: (for the sake of less typing, let [math]\displaystyle{ b=a^k }[/math])

[math]\displaystyle{ (b^{11}-1)/(b-1) = b^{10} + b^9 + b^8 + b^7 + b^6 + b^5 + b^4 + b^3 + b^2 + b + 1 }[/math]

We can multiply this by [math]\displaystyle{ b^{-5} }[/math]:

[math]\displaystyle{ b^5 + b^4 + b^3 + b^2 + b + 1 + b^{-1} + b^{-2} + b^{-3} + b^{-4} + b^{-5} }[/math]

and regroup

[math]\displaystyle{ b^5 + b^{-5} + b^4 + b^{-4} + b^3 + b^{-3} + b^2 + b^{-2} + b + b^{-1} + 1 }[/math] (1)

Now we'd like to replace [math]\displaystyle{ b^5+b^{-5} }[/math] by, say, [math]\displaystyle{ (b+b^{-1})^5 }[/math], but that gives us more terms than just [math]\displaystyle{ b^5+b^{-5} }[/math] due to the binomial theorem: [math]\displaystyle{ (b+b^{-1})^5 = b^5 + 5b^3 + 10b + 10b^{-1} + 5b^{-3} + b^{-5} }[/math], and we have [math]\displaystyle{ b^5+b^{-5} = (b+b^{-1})^5 - 5b^3 - 10b - 10b^{-1} - 5b^{-3} }[/math].

Fortunately, those extra terms are again of the form [math]\displaystyle{ c(b^n + b^{-n}) }[/math] and can be combined with the other summands of (1):

[math]\displaystyle{ \left((b+b^{-1})^5 - 5b^3 - 10b - 10b^{-1} - 5b^{-3}\right) + b^4 + b^{-4} + b^3 + b^{-3} + b^2 + b^{-2} + b + b^{-1} + 1 = ::(b+b^{-1})^5 + b^4 + b^{-4} - 4(b^3 + b^{-3}) + b^2 + b^{-2} - 9(b + b^{-1}) + 1 }[/math]

Handle the term [math]\displaystyle{ b^4 + b^{-4} }[/math] the same way, etc.

In the end, you'll have a polynomial

[math]\displaystyle{ c_5(b+b^{-1})^5 + c_4(b+b^{-1})^4 + c_3(b+b^{-1})^3 + c_2(b+b^{-1})^2 + c_1(b+b^{-1}) + c_0 }[/math].

Thus, you can use the quintic [math]\displaystyle{ c_5 x^5 + c_4 x^4 + c_3 x^3 + c_2 x^2 + c_1 x + c_0 }[/math] with root [math]\displaystyle{ b+1/b }[/math].

The siever input file wants the root as an integer, so you have to do a modular inversion: in Pari/GP, use Mod(b+1/b,N)

where you assigned N=(cofactor of [math]\displaystyle{ a^{11k}-1 }[/math]), b=(value of [math]\displaystyle{ a^k }[/math]) before. The result will be printed as

Mod(M,N)

where the value in place of M is the desired root.

The linear poly will be [math]\displaystyle{ x-(b+b^{-1}) }[/math]. Using [math]\displaystyle{ x-M }[/math] directly is no good as M is about as large as N itself, so the linear polynomial would have a far too large coefficient. Instead, multiply the polynomial by b:

[math]\displaystyle{ g(x) = bx - (b^2 + 1) }[/math]

Now the coefficients b and [math]\displaystyle{ (b^2+1) }[/math] are small enough.

The method for getting the coefficients of the algebraic polynomial above shows why we should do a change of variable to [math]\displaystyle{ b+b^{-1} }[/math], but it is a tedious way of actually getting the coefficients. It is easier to just set up a polynomial

[math]\displaystyle{ f(x)=a_5 x^5 + a_4 x^4 + a_3 x^3 + a_2 x^2 + a_1 x + a_0 }[/math],

and writing the difference

f(b+1/b)*b^5 - (b^11-1)/(b-1)

in Pari/GP (with b as a variable, not the value of [math]\displaystyle{ a^k }[/math]). This yields

[math]\displaystyle{ (a_5 - 1)b^{10} + (a_4 - 1)b^9 + \ldots + (a_4 - 1)b + (a_5 - 1) }[/math]

and we want the difference to be zero, so we can immediately set

[math]\displaystyle{ a_5 = 1 }[/math]

[math]\displaystyle{ a_4 = 1 }[/math]

Evaluating the difference again yields

[math]\displaystyle{ (a_3 + 4)b^8 + (a_2 + 3)b^7 + ... + (a_2 + 3)b^3 + (a_3 + 4)b^2 }[/math]

so we set

[math]\displaystyle{ a_3 = -4 }[/math]

[math]\displaystyle{ a_2 = -3 }[/math]

Now the difference is

[math]\displaystyle{ (a_1 - 3)b^6 + (a_0 - 1)b^5 + (a_1 - 3)b^4 }[/math]

so we set

[math]\displaystyle{ a_1 = 3 }[/math]

[math]\displaystyle{ a_0 = 1 }[/math]

This produces the polynomials

[math]\displaystyle{ f(x) = x^5 + x^4 - 4x^3 - 3x^2 + 3x + 1 }[/math]

[math]\displaystyle{ g(x) = bx - (b^2 + 1) }[/math]

with common root [math]\displaystyle{ M = b+1/b\ \pmod{N} }[/math] and [math]\displaystyle{ b=a^k }[/math].

Similarly for numbers of the form [math]\displaystyle{ a^{13k}-1 }[/math].

See also

• SNFS polynomial generation calculator