Evaluating isogenies in polylogarithmic time

Let ∶ → ′ be an N-isogeny between elliptic curves (or abelian varieties) over a finite field _. We show that there always exist an efficient representation of that takes polylogarithmic (log^(1) log ) space and which can evaluate at any point ∈ (_{^}) in polylogarithmic (log^(1) ) arithmetic operations in _{^}. Furthermore, this efficient representation can be computed by evaluating on (log ) points defined over extensions of degree (log ) over _. In particular, if is represented by the equation () = 0 of its kernel , then using Vélu’s formula the efficient representation can be computed in time ̃( log + log^2 )