Abstract
We propose an algorithm for computing an isogeny between two elliptic curves E₁,E₂ defined over a finite field such that there is an imaginary quadratic order O satisfying O≃ End(E_i) for i = 1,2. This concerns ordinary curves and supersingular curves defined over F_p (the latter used in the recent CSIDH proposal). Our algorithm has heuristic asymptotic run time e^O(√log(|Δ|)) and requires polynomial quantum memory and e^O(√log(|Δ|)) classical memory, where Δ is the discriminant of O. This asymptotic complexity outperforms all other available method for computing isogenies. We also show that a variant of our method has asymptotic run time e^O(√log(|Δ|)) while requesting only polynomial memory (both quantum and classical).