Non-linear polynomial selection for the number field sieve (Q412202): Difference between revisions

The Number Field Sieve (see [\textit{A. K. Lenstra} and \textit{H. W. Lenstra jun.} (eds.), The development of the number field sieve. Lecture Notes in Mathematics. 1554. Berlin: Springer-Verlag (1993; Zbl 0777.00017)]) is the best method today to factor a large integer \(N\). A first step is to find two polynomials \(f,g\in \mathbb{Z}[X]\) sharing a common root modulo \(N\)\, or equivalently with resultant \(\text{Res}(f,g)\) a (small) multiple of \(N\) (polynomial selection). Usually one takes \(g\) to be a linear polynomial and as \(f\) a polynomial of (small) degree \(d>1\). P. L. Montgomery (see \textit{M. Elkenbracht-Huizing} [Exp. Math. 5, No. 3, 231--253 (1996; Zbl 0869.11101)]) proposed a method producing polynomials \(f,g\) of degree two and recently \textit{R. S. Williams} [M. Sc. Thesis, Texas Tech. Univ. (1910)] gave an algorithm to select \(f,g\) with degree \(d=3\). The present paper generalizes Montgomery's method allowing to find polynomials of (the same) degree \(d\) for any \(d\). Section 1 reminds notations and basic facts about lattices and resultants and Section 2 summarizes the state of the art in polynomial selection, describing the Montgomery and Williams algorithms. Section 3 describes the proposed method giving details of the algorithm in the case \(d=3\). In this last case the authors conclude that their method improves Williams' algorithm because ``it finds two polynomials with resultant \(O(N^{5/4})\) instead of \(O(N^{4/3})\)''. Finally Section 4 discusses the open question of how to produce polynomials \(f,g\) of different degrees, in particular \(d\) and \(d-1\).