Deterministic root finding over finite fields using Graeffe transforms (Q300881)

Let us consider the finite field \(\mathbb{F}_q\) with \(q=p^k\) elements where \(p\) is a prime number and \(k\geq 1\). Suppose that \(f\in \mathbb{F}_q[x]\) is a polynomial such that all its irreducible factors are linear with multiplicity one. In the paper under review, the authors propose new deterministic algorithms, based on Graeffe transforms for computing all roots of \(f\). Furthermore, they present a new algorithm for computing characteristic polynomial of multiplication endomorphisms in finite field extensions.