Deterministic equation solving over finite fields

C. van de Woestijne


Deterministic algorithms are presented for the efficient solution of diagonal homogeneous equations in many variables over finite fields. As auxiliary algorithms, it is shown how to compute a field generator that is an $n$th power, and how to write elements as sums of $n$th powers, for a given integer $n$. All these algorithms take polynomial time in $n$ and the field size, and are practical as stated.