Deterministic root finding over finite fields using Graeffe transforms

We design new deterministic algorithms, based on Graeffe transforms, to compute all the roots of a polynomial which splits over a finite field $$\mathbb {F}_q$$ . Our algorithms were designed to be particularly efficient in the case when the cardinality $$q - 1$$ of the multiplicative group of $$\mathbb {F}_q$$ is smooth. Such fields are often used in practice because they support fast discrete Fourier transforms. We also present a new nearly optimal algorithm for computing characteristic polynomials of multiplication endomorphisms in finite field extensions. This algorithm allows for the efficient computation of Graeffe transforms of arbitrary orders.