Paper 2026/2661

Radical isogenies on every model

Abstract

Radical isogeny formulae compute a cyclic chain of $N$-isogenies with one $N$th root per step and without sampling torsion points, but for general $N$ they were only known in Tate normal form. We give radical steps of every odd degree $N$ directly on short Weierstrass, Montgomery, twisted Edwards, Huff, extended Jacobi quartic, twisted Hessian, Legendre and Jacobi intersection curves, on Kummer lines, and on all curves with a rational point of order~$2$. Our approach is model-independent. The Tate normal form data is obtained from the $x$-coordinate of the kernel generator by a shifted recursion, and the codomain is recovered in the original model by locating the image of a distinguished torsion point, without square roots. In Tate normal form we lower the cost of a step from $12.5N$ to $10N$ multiplications plus one exponentiation, and short Weierstrass curves come close at $10N+35$. Montgomery and twisted Edwards curves cost $10.5N+O(1)$. However, pushing a point through their steps costs only $2N$ multiplications without precomputation, against $2N+16$ plus a shared $2N-7$ in Tate normal form, which makes them the cheapest models for chains that transport torsion points, e.g.\ for all $N\ge19$ when two points are pushed. The other models cost between $11.5N+O(\log N)$ and $15.5N+O(\log N)$ per step. All algorithms are inversion-free, with exact operation counts.