Implementing the tangent Graeffe root finding method

Michael Monagan, CECM, Simon Fraser Univeristy

Talk Slides

Abstract:

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 implementation.

This is joint work with Joris van der Hoeven.