**Radical isogenies**

*Wouter Castryck and Thomas Decru and Frederik Vercauteren*

**Abstract: **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.

**Category / Keywords: **public-key cryptography / post-quantum cryptography, isogenies, Tate pairing, CSIDH

**Original Publication**** (in the same form): **IACR-ASIACRYPT-2020

**Date: **received 14 Sep 2020

**Contact author: **wouter castryck at kuleuven be, thomas decru@kuleuven be, frederik vercauteren@kuleuven be

**Available format(s): **PDF | BibTeX Citation

**Version: **20200915:113000 (All versions of this report)

**Short URL: **ia.cr/2020/1108

[ Cryptology ePrint archive ]