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 F_q, and suppose that there exists an isogeny [STIX]x1D713 between E and E^′ . We propose an algorithm that determines [STIX]x1D713 from the knowledge of E, E^′ and of its degree r, by using the structure of the -torsion of the curves (where 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 O (r^2)p^O(1) base field operations. On the other hand, the cost of our algorithm is O (r^2)(q)^O(1), for a large class of inputs; this makes it an interesting alternative for the medium- and large-characteristic cases.