Explicit isogenies in quadratic time in any characteristic. Issue Volume 19:Issue A(2016) (August 2016)

• Record Type: Journal Article
• Authors: De Feo, Luca; Hugounenq, Cyril; Plût, Jérôme; Schost, Éric
• Is Part Of: LMS journal of computation and mathematics. Volume 19:Issue A(2016)
• Page Start: 267
• Page End: 282
• Publication Date: 2016-08
• Subjects: 11Y40 (primary), -- 11G20, -- 14H52 (secondary)
• DOI: 10.1112/S146115701600036X
• Languages: English
• ISSNs: 1461-1570

Abstract

Abstract : Consider two ordinary elliptic curves $E, E^{\prime }$ defined over a finite field $\mathbb{F}_{q}$, and suppose that there exists an isogeny $\unicode[STIX]{x1D713}$ between $E$ and $E^{\prime }$ . We propose an algorithm that determines $\unicode[STIX]{x1D713}$ 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, 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.