Better polynomials for GNFS (Q2792346)

The General Number Field Sieve (GNFS) (see [\textit{A. K. Lenstra} (ed.) and \textit{H. W. Lenstra jun.} (ed.), The development of the number field sieve. Berlin: Springer-Verlag (1993; Zbl 0777.00017)] is the best known method to factor a large integer \(n\). The first step of the GNFS is \textit{polynomial selection}: to find two irreducible and coprime polynomials \(f(x), g(x)\in Z[X]\) sharing a common root modulo \(n\) or equivalently with resultant \(Res(f, g)\equiv 0 \bmod n\).NEWLINENEWLINEIn this paper, as usually, \(g\)\, is a linear polynomial and \(f\) a polynomial of (small) degree \(d>1\). (P. L. Montgomery and other authors proposed a method producing polynomials \(f,g\) of the same degree \(d\)). The running time of the GNFS method depends on the size and root properties of \(f\) and \(g\).NEWLINENEWLINEBeginning with some convenient \(f,g\) their size and root properties can be optimized using translation (\(f(x+k), g(x+k)\)) and rotation of \(f(x)\) by a polynomial \(\lambda(x)\) (\(f_{\lambda}(x)=f(x)+\lambda(x)g(x))\), see [\textit{B. A. Murphy}, Polynomial selection for the number field sieve integer factorisation algorithm. PhD thesis, The Australian National University (1999)]. The present paper deals with the size optimization step to produce polynomials with smaller logarithmic \(L^2\)-norm.NEWLINENEWLINESection 3 first describes some methods that produce polynomials with \(Res(f,g)=n\) and then proposes a generalization such that \(Res(f,g)=ln\), with \(l\) a small number. The algorithm, described for \(deg(f)=6\), takes \(f(x+k)\) for several values of \(k\) (Section 3.4 describes two methods to choose such \(k\)) and applies the Lenstra-Lenstra-Lovász (LLL) algorithm to find a good rotation of \(f(x+k)\). Table 1 shows numerical results with \(10^5\) sextic polynomials (for RSA-768) and 5795 quintic polynomials (for RSA-512). Finally Section 4 gives examples of polynomials for some RSA challenge numbers (RSA-768, RSA-896 and RSA-1024).