# Faster computation of isogenies of large prime degree

5 GRACE - Geometry, arithmetic, algorithms, codes and encryption
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France
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 $\tilde{O}(\ell)$ $\mathbb{F}_q$-operations, where the $\tilde{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 $\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.
Document type :
Conference papers
Domain :

Cited literature [29 references]

https://hal.inria.fr/hal-02514201
Contributor : Benjamin Smith Connect in order to contact the contributor
Submitted on : Saturday, March 21, 2020 - 5:54:27 PM
Last modification on : Friday, August 5, 2022 - 10:30:54 AM
Long-term archiving on: : Monday, June 22, 2020 - 1:06:13 PM

### Files

velusqrt-1.pdf
Files produced by the author(s)

### Citation

Daniel J. Bernstein, Luca de Feo, Antonin Leroux, Benjamin Smith. Faster computation of isogenies of large prime degree. ANTS-XIV - 14th Algorithmic Number Theory Symposium, Jun 2020, Auckland, New Zealand. pp.39-55, ⟨10.2140/obs.2020.4.39⟩. ⟨hal-02514201⟩

Record views