Paper 2025/189

Experimentally studying path-finding problem between conjugates in supersingular isogeny graphs: Optimizing primes and powers to speed-up cycle finding

Abstract

We study the problem of finding a path between conjugate supersingular elliptic curves, a sub-routine of cycle finding algorithm in the graph $\chi_l(\overline{\mathbb{F}_p})$ of all supersingular elliptic curves over $\mathbb{F}_{p^2}$, connected by $l$ isogenies for primes $l,p$. We prove that asymptotically the most time-efficient way of overviewing the graph to find conjugate paths is seeing $i(=3)$ steps together, a question posed in Remark 3.5 by Eisentr{\"a}ger \etal~\cite{eisentrager2020}. We see both theoretically and experimentally that selecting $l,i$ optimally speeds up the cycle finding.