Evaluating a polynomial on a set of points is a fundamental task in computer algebra. In this work, we revisit a particular variant called trimmed multipoint evaluation: given an n-variate polynomial with bounded individual degree d and total degree D, the goal is to evaluate it on a natural class of input points. This problem arises as a key subroutine in recent algorithmic results [Dinur; SODA’21], [Dell, Haak, Kallmayer, Wennmann; SODA’25]. It is known that trimmed multipoint evaluation can be solved in near-linear time [van der Hoeven, Schost; AAECC’13] by a clever yet somewhat involved algorithm. We give a simple recursive algorithm that avoids heavy computer-algebraic machinery, and can be readily understood by researchers without specialized background.

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 𝔽2 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 𝔽2 and is significantly faster than the one of Lokshtanov et al. for q > 2.