Getting to the right root: radical isogenies of every degree
:12
Abstract
Class group actions on supersingular elliptic curves over $\mathbb F_p$ as in CSIDH are typically evaluated as long chains of isogenies of small prime degree. Radical isogeny formulae compute such chains using a single $N$th root per step, without sampling torsion points. Compact formulae of linear size had been conjectured for all odd $N$. We prove a corrected version of these formulae for every $N\ge4$, odd and even, over every field of characteristic coprime to $2N$. In our formulation, every building block is a twisted sum of a discrete Kronecker function over $\mathbb Z/N\mathbb Z$, and the formulae follow from a distribution relation for the Kronecker theta function. For even $N$, the $N$th root is only determined up to sign over $\mathbb F_p$, and the sign decides whether the walk stays on the surface of the $2$-isogeny volcano. We show that the radical times a $2$-torsion coordinate of the next curve is a square, which yields the horizontal choice for all even $N$; previously this was only known for $N\le14$. Algorithmically, one radical step costs about $12.5N$ multiplications and one exponentiation, without inversions. For horizontal $2$-isogeny walks, radical $2^m$-isogenies with $m\in\{5,6,7\}$ are optimal for primes of $512$ to $4096$ bits. Finally, we show how to evaluate radical isogenies on points. As a consequence, a class group action can be computed from two given points, one on the curve and one on its quadratic twist, without ever sampling torsion points.