Elliptic Butterflies

Some evaluation/interpolation problems have a particularly efficient solution.

The Cooley-Tuckey (butterflies) recursive algorithm, first introduced by Gauss, allows fast evaluation of a degree d polynomial at d-th roots of unity when d is a power of 2. This algorithm is widely used in fast arithmetic.

I will present a joint work with Reynald Lercier about an elliptic analogue of this method, and its applications.

## Résumé en Français

Certains problèmes d'évaluation/interpolation admettent une résolution particulièrement rapide.

La méthode récursive des papillons de Cooley-Tuckey, introduite pas Gauss, permet en particulier d'évaluer un polynôme de degré plus petit que d en les racines d-ièmes

de l'unité, en temps dlog(d) si d est une puissance de 2. Un grand nombre d'algorithmes rapides reposent plus ou moins directement sur cette méthode.

Dans cet exposé je présenterai un travail commun avec Reynald Lercier sur un équivalent elliptique de cette méthode et sur ses applications.