Solving Polynomial Equations Over Finite Fields

We present a randomized algorithm for solving low-degree polynomial equation systems over finite fields faster than exhaustive search. In order to do so, we follow a line of work by Lokshtanov, Paturi, Tamaki, Williams, and Yu (SODA 2017), Björklund, Kaski, and Williams (ICALP 2019), and Dinur (SODA 2021). In particular, we generalize Dinur’s algorithm for F2 to all finite fields, in particular the “symbolic interpolation” of Björklund, Kaski, and Williams, and we use an efficient trimmed multipoint evaluation and interpolation procedure for multivariate polynomials over finite fields by Van der Hoeven and Schost (AAECC 2013). The running time of our algorithm matches that of Dinur’s algorithm for F2 and is significantly faster than the one of Lokshtanov et al. for q > 2.

We complement our results with tight conditional lower bounds that, surprisingly, we were not able to find in the literature. In particular, under the strong exponential time hypothesis, we prove that it is impossible to solve n-variate low-degree polynomial equation systems over Fq in time O((q −ε) n). As a bonus, we show that under the counting version of the strong exponential time hypothesis, it is impossible to compute the number of roots of a single n-variate low-degree polynomial over Fq in time O((q − ε)n); this generalizes a result of Williams (SOSA 2018) from F2 to all finite fields.