The tangent Graeffe method has been developed for the efficient computation of single roots of polynomials over finite fields with multiplicative groups of smooth order. It is a key ingredient of sparse interpolation using geometric progressions, in the case when blackbox evaluations are comparatively cheap. In this paper, we improve the complexity of the method by a constant factor and we report on a new implementation of the method and a first parallel implemenation.

Authors: Joris van der Hoeven, Michael Monagan

View: Html, TeXmacs, Pdf, BibTeX

Shortened ICMS version: Pdf

Note: an extended version that also corrects a nasty sign error can be found here.