Elliptic butterflies

Overview & Synopsis

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 in d log(d) for these problems and present applications to finite field arithmetic, coding theory and cryptography.