Skip to Main content Skip to Navigation
Conference papers

Faster computation of isogenies of large prime degree

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.
Complete list of metadata

Cited literature [29 references]  Display  Hide  Download

https://hal.inria.fr/hal-02514201
Contributor : Benjamin Smith <>
Submitted on : Saturday, March 21, 2020 - 5:54:27 PM
Last modification on : Friday, April 30, 2021 - 9:52:54 AM
Long-term archiving on: : Monday, June 22, 2020 - 1:06:13 PM

Files

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

Identifiers

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⟩

Share

Metrics

Record views

194

Files downloads

614