Explicit isogenies in quadratic time in any characteristic

Abstract

Consider two elliptic curves $E,E^{\prime }$ defined over the finite field ${\mathbb{F}}_q$, and suppose that there exists an isogeny $\psi$ between $E$ and $E^{\prime }$. We propose an algorithm that determines $\psi$ from the knowledge of $E$, $E^{\prime }$ and of its degree $r$, by using the structure of the $\ell$-torsion of the curves (where $\ell$ is a prime different from the characteristic $p$ of the base field). Our approach is inspired by a previous algorithm due to Couveignes, that involved computations using the $p$-torsion on the curves. The most refined version of that algorithm, due to De Feo, has a complexity of $\tilde{O}(r^2)p^{O(1)}$ base field operations. On the other hand, the cost of our algorithm is $\tilde{O}(r^2+\sqrt{r}\log (q))$; this makes it an interesting alternative for the medium- and large-characteristic cases.

16 pages, 3 figures, submitted to ANTS-XII, modified version with analysis for the choice of \ell and new experimental plots