Bounds on Heights of $2$-isogeny Graphs in Ordinary Curves over ${\mathbb{F}}_p$ and ${\mathbb{F}}_{p^2}$ and Its Application

Abstract

It is known that any isogeny graph consisting of ordinary elliptic curves over ${\mathbb{F}}_q$ with $q=p$ or $p^2$ has a special structure, called a volcano graph. We have a bound $h<{\log }_2\sqrt{4q}$ of a height $h$ of the $2$-volcano graph. In this paper, we improve the bound on a height of $2$-volcano graphs over ${\mathbb{F}}_q$. In case $q=p^2$, we show a tighter bound $h\le \lfloor \frac{1}{2}\lfloor {\log }_{2}p\rfloor \rfloor +2$. In case $q=p$, we also show that a good bound for each prime $p$ can be computed by using our proposed techniques.