### Faster computation of isogenies of large prime degree

Daniel J. Bernstein, Luca De Feo, 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.

##### Metadata
Available format(s)
Category
Implementation
Publication info
Preprint. MINOR revision.
Keywords
isogenieselliptic curve cryptographynumber theorypublic key cryptography
Contact author(s)
authorcontact-velusqrt @ box cr yp to
History
2020-03-23: last of 2 revisions
2020-03-22: received
See all versions
Short URL
https://ia.cr/2020/341
License

CC BY

BibTeX

@misc{cryptoeprint:2020/341,
author = {Daniel J.  Bernstein and Luca De Feo and Antonin Leroux and Benjamin Smith},
title = {Faster computation of isogenies of large prime degree},
howpublished = {Cryptology ePrint Archive, Paper 2020/341},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/341}},
url = {https://eprint.iacr.org/2020/341}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.