On the complexity exponent of polynomial system solving (Q2658549)

The authors present a probabilistic Las Vegas algorithm for solving sufficiently generic square polynomial systems over finite fields. For \(\mathbb{K}\) an effective field, consider a homogeneous system of polynomial equations \(f_1=\dots =f_n=0\), where \(f_i\in \mathbb{K}[x_0,\dots ,x_n]\), deg\(f_i\geq 2\), and the exact resolution of such a system through the computation of a parametrization of its zero set by a so-called primitive element. The algorithm requires \(f_1, \dots, f_n\) to be a regular sequence and the intermediate ideals \(I_i:=(f_1,\dots ,f_i)\), \(1\leq i\leq n\), to be absolutely radical, that is radical over the algebraic closure of \(\mathbb{K}\). The authors achieve a nearly quadratic running time in the number of solutions, for densely represented input polynomials, and prove a nearly linear bit complexity bound for polynomial systems with rational coefficients. The results are obtained using the combination of the Kronecker solver and a new improved algorithm for fast multivariate modular composition.