On nonlinear polynomial selection and geometric progression (mod \(N\)) for number field sieve (Q2787639)

A first step of the Number Field Sieve method to factor an integer \(N\) is to find two polynomials \(f,g\in \mathbb{Z}[X]\) sharing a common root modulo \(N\), see \textit{A. K. Lenstra} and \textit{H. W. Lenstra} (eds.) [Lect. Notes Math. 1554. Berlin: Springer Verlag (1993; Zbl 0777.00017)]. Usually one takes as \(f\) a nonlinear polynomial of small degree \(d>1\) and as \(g\) a linear one (linear polynomial selection) but 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 \(d\geq 2\) (nonlinear polynomial selection).NEWLINENEWLINENEWLINEMontgomery's method finds \(f,g\) given a geometric progression modulo \(N\) \([c_0,\dots, c_{2d-2}]\) of length \(2d-1\) and \(c_i=O(N^{1-1/d})\). Montgomery shows how to construct such \(\text{GP} \pmod N\) when \(d=2\). The present paper proposes some generalizations of the Montgomery's method.NEWLINENEWLINENEWLINESection 3 uses \(\text{GP}\pmod N\) of length \(d+k\), \(1\leq k\leq d-1\), allowing to find polynomials \(f,g\) with degree \(d\) sharing a common root modulo \(N\) for \(l/2<d<l\) for a GP of length \(l\). Theorems 1 and 2 show the relations between \(\text{GP}\pmod N\) and pairs of polynomials \(f,g\), the number of such pairs and the size of their coefficients. Section 3 studies the classes of GP of length \(d+1\) and \(d+2\) and provides examples of both types.