https://www.rieselprime.de/z/index.php?title=SNFS_polynomial_selection&feed=atom&action=history SNFS polynomial selection - Revision history 2021-10-26T09:43:49Z Revision history for this page on the wiki MediaWiki 1.31.1 https://www.rieselprime.de/z/index.php?title=SNFS_polynomial_selection&diff=1022&oldid=prev Karbon: restored 2019-02-12T16:14:20Z <p>restored</p> <p><b>New page</b></p><div>For the [[special number field sieve|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).<br /> <br /> ==Cyclotomic numbers==<br /> For cyclotomic numbers, there are four standard operations you can perform on the number to derive suitable polynomials:<br /> #Multiplying by a constant<br /> #Increasing or decreasing a power<br /> #Dividing out algebraic factors<br /> #halving the degree of a symmetric polynomial<br /> <br /> 1. Suppose you want to factor a number of the form &lt;math&gt;a^{59}-1&lt;/math&gt; for a given ''a'' with a quintic (a degree 5 polynomial). You can multiply ''N'' by ''a'' and get &lt;math&gt;aN=a^{60}-a&lt;/math&gt;, which you can express as &lt;math&gt;x^5-a&lt;/math&gt; with root &lt;math&gt;m=a^{12}&lt;/math&gt;. For example, the smallest &lt;math&gt;a^{59}-1&lt;/math&gt; number currently not completely factored is &lt;math&gt;208^{59}-1&lt;/math&gt;, the polynomials would be &lt;math&gt;x^5-208&lt;/math&gt; on the algrebraic side and &lt;math&gt;x-6557827967253220516257857536&lt;/math&gt; on the rational side. Multiplying ''N'' by a constant increases the [[SNFS difficulty]] of the factorisation.<br /> <br /> 2. If you want to factor &lt;math&gt;a^{61}-1&lt;/math&gt;, you can rewrite the power as &lt;math&gt;a\cdot a^{60}&lt;/math&gt; and get &lt;math&gt;a\cdot a^{60}-1&lt;/math&gt;, or &lt;math&gt;a x^5-1&lt;/math&gt;, again with root &lt;math&gt;m=a^{12}&lt;/math&gt;. Thus, your polynomials are, for example for &lt;math&gt;N=208^{61}-1&lt;/math&gt;, &lt;math&gt;208x^5-1&lt;/math&gt; and &lt;math&gt;x-6557827967253220516257857536&lt;/math&gt;.<br /> <br /> 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.<br /> <br /> You can also combine both methods if the base is composite. If you want to factor, say, &lt;math&gt;10^{113}-1&lt;/math&gt; with a quintic, you could use &lt;math&gt;1000x^5-1&lt;/math&gt; (difficulty 113) or &lt;math&gt;x^5-100&lt;/math&gt; (difficulty 115) by the method of 1. or 2. alone.<br /> <br /> But you can also first multiply ''N'' by &lt;math&gt;5^2&lt;/math&gt; to get &lt;math&gt;25N=2^{113} \cdot 5^{115} - 25&lt;/math&gt;, then rewrite as &lt;math&gt;8 (2^{110} 5^{115}) - 25&lt;/math&gt;, or &lt;math&gt;8x^5-25&lt;/math&gt;, with root &lt;math&gt;m=2^{22} \cdot 5^{23}&lt;/math&gt; (difficulty ~114). So your polynomials are &lt;math&gt;8x^5-25&lt;/math&gt; and &lt;math&gt;x-50000000000000000000000&lt;/math&gt;. 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.<br /> <br /> 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.<br /> <br /> *&lt;math&gt;(a^{3k}-1)/(a^k-1) = a^{2k} + a^k + 1&lt;/math&gt; which can be converted to a quadratic &lt;math&gt;x^2+x+1&lt;/math&gt; with root &lt;math&gt;a^k&lt;/math&gt;. However, a quadratic has too small degree, the coefficients on the rational side would become huge. Instead, if ''k'' is odd, we write &lt;math&gt;a^2\cdot a^{2(k-1)} + a\cdot a^{k-1} + 1&lt;/math&gt; and can convert to a quartic in &lt;math&gt;a^{(k-1)/2}&lt;/math&gt;. 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.<br /> *&lt;math&gt;(a^{5k}-1)/(a^k-1) = a^{4k} + a^{3k} + a^{2k} + a^k + 1&lt;/math&gt;, which is a useable quartic in &lt;math&gt;a^k&lt;/math&gt;.<br /> *&lt;math&gt;(a^{7k}-1)/(a^k-1) = a^{6k} + a^{5k} + a^{4k} + a^{3k} + a^{2k} + a^k + 1&lt;/math&gt;, which is a useable sextic in &lt;math&gt;a^k&lt;/math&gt;.<br /> <br /> 4. For &lt;math&gt;a^{11k}-1&lt;/math&gt; and &lt;math&gt;a^{13k}-1&lt;/math&gt; you'd get degrees 10 and 12, respectively - too large. But the resulting polynomial is symmetric: (for the sake of less typing, let &lt;math&gt;b=a^k&lt;/math&gt;)<br /> :&lt;math&gt;(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&lt;/math&gt;<br /> <br /> We can multiply this by &lt;math&gt;b^{-5}&lt;/math&gt;:<br /> :&lt;math&gt;b^5 + b^4 + b^3 + b^2 + b + 1 + b^{-1} + b^{-2} + b^{-3} + b^{-4} + b^{-5}&lt;/math&gt;<br /> and regroup<br /> :&lt;math&gt;b^5 + b^{-5} + b^4 + b^{-4} + b^3 + b^{-3} + b^2 + b^{-2} + b + b^{-1} + 1&lt;/math&gt; (1)<br /> <br /> Now we'd like to replace &lt;math&gt;b^5+b^{-5}&lt;/math&gt; by, say, &lt;math&gt;(b+b^{-1})^5&lt;/math&gt;, but that gives us more terms than just &lt;math&gt;b^5+b^{-5}&lt;/math&gt; due to the binomial theorem: &lt;math&gt;(b+b^{-1})^5 = b^5 + 5b^3 + 10b + 10b^{-1} + 5b^{-3} + b^{-5}&lt;/math&gt;, and we have &lt;math&gt;b^5+b^{-5} = (b+b^{-1})^5 - 5b^3 - 10b - 10b^{-1} - 5b^{-3}&lt;/math&gt;.<br /> <br /> Fortunately, those extra terms are again of the form &lt;math&gt;c(b^n + b^{-n})&lt;/math&gt; and can be combined with the other summands of (1):<br /> <br /> :&lt;math&gt;\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 =<br /> ::(b+b^{-1})^5 + b^4 + b^{-4} - 4(b^3 + b^{-3}) + b^2 + b^{-2} - 9(b + b^{-1}) + 1&lt;/math&gt;<br /> <br /> Handle the term &lt;math&gt;b^4 + b^{-4}&lt;/math&gt; the same way, etc.<br /> <br /> In the end, you'll have a polynomial<br /> :&lt;math&gt;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&lt;/math&gt;.<br /> <br /> Thus, you can use the quintic &lt;math&gt;c_5 x^5 + c_4 x^4 + c_3 x^3 + c_2 x^2 + c_1 x + c_0&lt;/math&gt; with root &lt;math&gt;b+1/b&lt;/math&gt;.<br /> <br /> The siever input file wants the root as an integer, so you have to do a modular inversion: in [http://pari.math.u-bordeaux.fr/ Pari/GP], use Mod(b+1/b,N)<br /> <br /> where you assigned N=(cofactor of &lt;math&gt;a^{11k}-1&lt;/math&gt;), b=(value of &lt;math&gt;a^k&lt;/math&gt;) before. The result will be printed as<br /> :Mod(M,N)<br /> <br /> where the value in place of M is the desired root.<br /> <br /> The linear poly will be &lt;math&gt;x-(b+b^{-1})&lt;/math&gt;. Using &lt;math&gt;x-M&lt;/math&gt; 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'':<br /> :&lt;math&gt;g(x) = bx - (b^2 + 1)&lt;/math&gt;<br /> Now the coefficients ''b'' and &lt;math&gt;(b^2+1)&lt;/math&gt; are small enough.<br /> <br /> The method for getting the coefficients of the algebraic polynomial above shows why we should do a change of variable to &lt;math&gt;b+b^{-1}&lt;/math&gt;, but it is a tedious way of actually getting the coefficients. It is easier to just set up a polynomial<br /> :&lt;math&gt;f(x)=a_5 x^5 + a_4 x^4 + a_3 x^3 + a_2 x^2 + a_1 x + a_0&lt;/math&gt;,<br /> and writing the difference<br /> :f(b+1/b)*b^5 - (b^11-1)/(b-1)<br /> <br /> in [http://pari.math.u-bordeaux.fr/ Pari/GP] (with ''b'' as a variable, not the value of &lt;math&gt;a^k&lt;/math&gt;). This yields<br /> :&lt;math&gt;(a_5 - 1)b^{10} + (a_4 - 1)b^9 + \ldots + (a_4 - 1)b + (a_5 - 1)&lt;/math&gt;<br /> <br /> and we want the difference to be zero, so we can immediately set<br /> :&lt;math&gt;a_5 = 1&lt;/math&gt;<br /> :&lt;math&gt;a_4 = 1&lt;/math&gt;<br /> <br /> Evaluating the difference again yields<br /> :&lt;math&gt;(a_3 + 4)b^8 + (a_2 + 3)b^7 + ... + (a_2 + 3)b^3 + (a_3 + 4)b^2&lt;/math&gt;<br /> <br /> so we set<br /> :&lt;math&gt;a_3 = -4&lt;/math&gt;<br /> :&lt;math&gt;a_2 = -3&lt;/math&gt;<br /> <br /> Now the difference is<br /> :&lt;math&gt;(a_1 - 3)b^6 + (a_0 - 1)b^5 + (a_1 - 3)b^4&lt;/math&gt;<br /> <br /> so we set<br /> :&lt;math&gt;a_1 = 3&lt;/math&gt;<br /> :&lt;math&gt;a_0 = 1&lt;/math&gt;<br /> <br /> This produces the polynomials<br /> :&lt;math&gt;f(x) = x^5 + x^4 - 4x^3 - 3x^2 + 3x + 1&lt;/math&gt;<br /> :&lt;math&gt;g(x) = bx - (b^2 + 1)&lt;/math&gt;<br /> <br /> with common root &lt;math&gt;M = b+1/b\ \pmod{N}&lt;/math&gt; and &lt;math&gt;b=a^k&lt;/math&gt;.<br /> <br /> Similarly for numbers of the form &lt;math&gt;a^{13k}-1&lt;/math&gt;.<br /> <br /> ==See also==<br /> *[[SNFS polynomial generation calculator]]<br /> [[Category:Factorization]]</div> Karbon