Implementing the tangent Graeffe root finding method


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.