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 $$ optimally speeds up the cycle finding.