**Faster computation of isogenies of large prime degree**

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

**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}' = \mathcal{E}/\langle{P}\rangle$ and rational maps defining a quotient isogeny $\phi: \mathcal{E} \to \mathcal{E}'$ in $\widetilde{O}(\ell)$ $\mathbb{F}_q$-operations, where the $\widetilde{O}$ is uniform in $q$.
This article shows how to compute $\mathcal{E}'$, and $\phi(Q)$ for $Q$ in $\mathcal{E}(\mathbb{F}_q)$, using only $\widetilde{O}(\sqrt{\ell})$ $\mathbb{F}_q$-operations, where the $\widetilde{O}$ is again uniform in $q$.
As an application, this article speeds up some computations used in the isogeny-based cryptosystems CSIDH and CSURF.

**Category / Keywords: **implementation / isogenies; elliptic curve cryptography; number theory; public key cryptography

**Date: **received 21 Mar 2020, last revised 23 Mar 2020

**Contact author: **authorcontact-velusqrt at box cr yp to

**Available format(s): **PDF | BibTeX Citation

**Version: **20200323:183508 (All versions of this report)

**Short URL: **ia.cr/2020/341

[ Cryptology ePrint archive ]