Elliptic butterflies

Abstract

We study natural evaluation and interpolation problems for elliptic functions and prove that they allow a recursive treatment using a variant of classical butterflies first introduced by Gauss. We deduce the existence of straight-line programs with complexity scaling with $d\log (d)$ for these problems and present applications to finite field arithmetic, coding theory and cryptography.

To be published in Journal of Complexity