#### Vol. 4, No. 1, 2020

 Recent Volumes 5: Gauge Theory and Low-Dimensional Topology 4: ANTS XIV 3: Hillman: Poincaré Duality 2: ANTS XIII 1: ANTS X
 The Open Book Series All Volumes About the Series Ethics Statement Purchase Printed Copies Author Index ISSN (electronic): 2329-907X ISSN (print): 2329-9061 MSP Books and Monographs Other MSP Publications
Faster computation of isogenies of large prime degree

### Daniel J. Bernstein, Luca De Feo, Antonin Leroux and Benjamin Smith

Vol. 4 (2020), No. 1, 39–55
##### Abstract

Let $\mathsc{ℰ}∕{\mathbb{𝔽}}_{q}$ be an elliptic curve, and $P$ a point in $\mathsc{ℰ}\left({\mathbb{𝔽}}_{q}\right)$ of prime order $\ell$. Vélu’s formulæ let us compute a quotient curve ${\mathsc{ℰ}}^{\prime }=\mathsc{ℰ}∕⟨P⟩$ and rational maps defining a quotient isogeny $\varphi :\mathsc{ℰ}\to {\mathsc{ℰ}}^{\prime }$ in $\stackrel{˜}{O}\left(\ell \right)$ ${\mathbb{𝔽}}_{q}$-operations, where the $\stackrel{˜}{O}$ is uniform in $q$. This article shows how to compute ${\mathsc{ℰ}}^{\prime }$, and $\varphi \left(Q\right)$ for $Q$ in $\mathsc{ℰ}\left({\mathbb{𝔽}}_{q}\right)$, using only $\stackrel{˜}{O}\left(\sqrt{\ell }\right)$ ${\mathbb{𝔽}}_{q}$-operations, where the $\stackrel{˜}{O}$ is again uniform in $q$. As an application, this article speeds up some computations used in the isogeny-based cryptosystems CSIDH and CSURF.

 Dedicated to the memory of Peter Lawrence Montgomery
##### Keywords
isogenies, resultants
Primary: 11Y16