Better polynomials for GNFS
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).
- Factoring estimates for a 1024-bit RSA modulus
- Factorization of a 768-Bit RSA Modulus
- scientific article; zbMATH DE number 1186938 (Why is no real title available?)
- scientific article; zbMATH DE number 475433 (Why is no real title available?)
- scientific article; zbMATH DE number 475434 (Why is no real title available?)
- scientific article; zbMATH DE number 1444326 (Why is no real title available?)
- Integers without large prime factors
- On polynomial selection for the general number field sieve
- Root optimization of polynomials in the number field sieve
- Smooth numbers: computational number theory and beyond
- Some mathematical remarks on the polynomial selection in NFS
- The development of the number field sieve
- The Multiple Polynomial Quadratic Sieve
- Comparing the difficulty of factorization and discrete logarithm: a 240-digit experiment
- On nonlinear polynomial selection and geometric progression (mod N) for number field sieve
- On polynomial selection for the general number field sieve
- Non-linear polynomial selection for the number field sieve
- A new ranking function for polynomial selection in the number field sieve
- Root optimization of polynomials in the number field sieve
- Optimal Parameterization of SNFS
- Higher-dimensional sieving for the number field sieve algorithms
- On the complexity formulae of the number field sieve and its variants
- Parallel structured Gaussian elimination for the number field sieve
- Montgomery's method of polynomial selection for the number field sieve
This page was built for publication: Better polynomials for GNFS
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2792346)
