Paper 2020/1108

Radical isogenies

Wouter Castryck, Thomas Decru, and Frederik Vercauteren


This paper introduces a new approach to computing isogenies called "radical isogenies" and a corresponding method to compute chains of $N$-isogenies that is very efficient for small $N$. The method is fully deterministic and completely avoids generating $N$-torsion points. It is based on explicit formulae for the coordinates of an $N$-torsion point $P'$ on the codomain of a cyclic $N$-isogeny $\varphi : E \to E'$, such that composing $\varphi$ with $E' \to E' / \langle P' \rangle$ yields a cyclic $N^2$-isogeny. These formulae are simple algebraic expressions in the coefficients of $E$, the coordinates of a generator $P$ of $\ker \varphi$, and an $N$th root $\sqrt[N]{\rho}$, where the radicand $\rho$ itself is given by an easily computable algebraic expression in the coefficients of $E$ and the coordinates of $P$. The formulae can be iterated and are particularly useful when computing chains of $N$-isogenies over a finite field $\mathbb{F}_q$ with $\gcd(q-1, N) = 1$, where taking an $N$th root is a simple exponentiation. Compared to the state-of-the-art, our method results in an order of magnitude speed-up for $N \leq 13$; for larger $N$, the advantage disappears due to the increasing complexity of the formulae. When applied to CSIDH, we obtain a speed-up of about $19 \%$ over the implementation by Bernstein, De Feo, Leroux and Smith for the CSURF-512 parameters.

Available format(s)
Public-key cryptography
Publication info
Published by the IACR in ASIACRYPT 2020
post-quantum cryptographyisogeniesTate pairingCSIDH
Contact author(s)
wouter castryck @ kuleuven be
thomas decru @ kuleuven be
frederik vercauteren @ kuleuven be
2021-06-03: last of 2 revisions
2020-09-15: received
See all versions
Short URL
Creative Commons Attribution


      author = {Wouter Castryck and Thomas Decru and Frederik Vercauteren},
      title = {Radical isogenies},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1108},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.