Paper 2024/971

A Note on (2, 2)-isogenies via Theta Coordinates

Abstract

In this paper, we revisit the algorithm for computing chains of $(2,2)$-isogenies between products of elliptic curves via theta coordinates proposed by Dartois et al. For each fundamental block of this algorithm, we provide a explicit inversion-free version. Besides, we exploit a novel technique of $x$-only ladder to speed up the computation of gluing isogeny. Finally, we present a mixed optimal strategy, which combines the inversion-elimination tool with the original methods together to execute a chain of $$-isogenies. We make a cost analysis and present a concrete comparison between ours and the previously known methods for inversion elimination. Furthermore, we implement the mixed optimal strategy for benchmark. The results show that when computing $$-isogeny chains with lengths of 126, 208 and 632, compared to Dartois, Maino, Pope and Robert's original implementation, utilizing our techniques can reduce $$, $$ and $$ multiplications over the base field $$, respectively. Even for the updated version which employs their inversion-free methods, our techniques still possess a slight advantage.