[Resource Topic] 2020/341: Faster computation of isogenies of large prime degree

Welcome to the resource topic for 2020/341

Faster computation of isogenies of large prime degree

Authors: Daniel J. Bernstein, Luca De Feo, Antonin Leroux, Benjamin Smith


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.

ePrint: https://eprint.iacr.org/2020/341

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .