Approximate GCD of several univariate polynomials with small degree perturbations (Q412204): Difference between revisions

A problem of interest in cryptanalysis is the following: given two integer numbers, find in polynomial time all perturbations of the two of them within a fixed number of bits, in such a way that the perturbed numbers can achieve a large GCD (see for instance [\textit{N. Howgrave-Graham}, Lect. Notes Comput. Sci. 2146, 51--66 (2001; Zbl 1006.94528)]). The polynomial counterpart of this problem has been studied in [\textit{J. von zur Gathen, M. Mignotte} and \textit{I. E. Shparlinski}, J. Symb. Comput. 45, No. 8, 879--886 (2010; Zbl 1248.11106)]. In the paper under review, a more general situation of the polynomial associated problem is considered. In more precise terms, given a sequence of univariate polynomials \(f_0,\ldots, f_s\) with coefficients in a field, and a degree bound for the perturbation problem, under some genericity assumptions the authors show that there ia an algorithm which solves the perturbation problem with \(\tilde{\mathcal{O}}(s^3n^2)\) field operations. Here, \(n=\max_{0\leq i\leq s}\{\deg(f_i)\}\).