Ordinary 3-Isogeny Graphs and Improvement of Supersingularity Testing for Twisted Hessian Curves over Prime Fields

Abstract

For any primes $p\ne \ell$, $\ell$-isogeny graphs of ordinary elliptic curves defined over ${\mathbb{F}}_{p^2}$ have a typical structure called $\ell$-volcanoes, and the structure is the core of Sutherland's supersingularity testing algorithm for elliptic curves. In this paper, by exploiting the properties of $3$-isogenies between twisted Hessian curves, we show that when $p\equiv 2(\mathrm{mod}3)$ and $\ell =3$, every ordinary twisted Hessian curve defined over ${\mathbb{F}}_p$ lies on the surface of the $3$-volcano. As an application, we give an improved version of Sutherland's supersingularity testing algorithm specialized to twisted Hessian curves defined over ${\mathbb{F}}_p$ with $p\equiv 2(\mathrm{mod}3)$. We also give a generalization of the known fact that any supersingular $j$-invariant is a cube in ${\mathbb{F}}_{p^2}$; we show that for any twisted Hessian curve $H(a,d)$ defined over ${\mathbb{F}}_{p^2}$, its $j$-invariant is not a cube in ${\mathbb{F}}_{p^2}$ if and only if $H(a,d)$ is ordinary and lies on the floor of a $3$-volcano.