Abstract

Let $\mathcal{ℰ}∕{\mathbb{𝔽}}_q$ be an elliptic curve, and $P$ a point in $\mathcal{ℰ}\left({\mathbb{𝔽}}_q\right)$ of prime order $\ell$. Vélu’s formulæ let us compute a quotient curve ${\mathcal{ℰ}}^{\prime }=\mathcal{ℰ}∕⟨P⟩$ and rational maps defining a quotient isogeny $\varphi :\mathcal{ℰ}\to {\mathcal{ℰ}}^{\prime }$ in $\tilde{O}\left(\ell \right)$ ${\mathbb{𝔽}}_q$-operations, where the $\tilde{O}$ is uniform in $q$. This article shows how to compute ${\mathcal{ℰ}}^{\prime }$, and $\varphi \left(Q\right)$ for $Q$ in $\mathcal{ℰ}\left({\mathbb{𝔽}}_q\right)$, using only $\tilde{O}\left(\sqrt{\ell }\right)$ ${\mathbb{𝔽}}_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.

Keywords

Mathematical Subject Classification

Milestones

Authors