Explicit isogenies in quadratic time in any characteristic

Abstract: Consider two elliptic curves

E, E^{'}

defined over the finite field

m a t h b b F_{q}

, and suppose that there exists an isogeny

p s i

between

E

and

E^{'}

. We propose an algorithm that determines

p s i

from the knowledge of

E

,

E^{'}

and of its degree

r

, by using the structure of the

e l l

-torsion of the curves (where

e l l

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

i l d e O (r^{2}) p^{O (1)}

base field operations. On the other hand, the cost of our algorithm is

i l d e O (r^{2} + s q r t r l o g (q))

; this makes it an interesting alternative for the medium- and large-characteristic cases.

Recommendations

Cites Work

Cited In (15)

This page was built for publication: Explicit isogenies in quadratic time in any characteristic