Faster computation of isogenies of large prime degree

Abstract

Let $\mathcal{E}/{\mathbb{F}}_q$ be an elliptic curve, and $P$ a point in $\mathcal{E}({\mathbb{F}}_q)$ of prime order $\ell$. Vélu's formulae let us compute a quotient curve ${\mathcal{E}}^{\prime }=\mathcal{E}/⟨P⟩$ and rational maps defining a quotient isogeny $\ddot{I}•:\mathcal{E}\to {\mathcal{E}}^{\prime }$ in $\tilde{O}(\ell )$ ${\mathbb{F}}_q$-operations, where the $\tilde{O}$ is uniform in $q$.This article shows how to compute ${\mathcal{E}}^{\prime }$, and $\ddot{I}•(Q)$ for $Q$ in $\mathcal{E}({\mathbb{F}}_q)$, using only $\tilde{O}(\sqrt{\ell })$ ${\mathbb{F}}_q$-operations, where the $\tilde{O}$ is again uniform in $q$.As an application, this article speeds up some computations used in the isogeny-based cryptosystems CSIDH and CSURF.