Explicit isogenies in quadratic time in any characteristic. Issue Volume 19:Issue A(2016) (August 2016) - De Feo, Luca; Hugounenq, Cyril; Plût, Jérôme; Schost, Éric
Abstract : Consider two ordinary elliptic curves $E, E^{′ }$ defined over a finite field $\mathbb{F}_{q}$, and suppose that there exists an isogeny $\unicode[STIX]{x1D713}$ between $E$ and $E^{′ }$ . We propose an algorithm that determines $\unicode[STIX]{x1D713}$ from the knowledge of $E$, $E^{′ }$ 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, which 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})\log (q)^{O(1)}$, for a large class of inputs; this makes it an interesting alternative for the medium- and large-characteristic cases.