On isogeny graphs of supersingular elliptic curves over finite fields (Q1633305)

Let \(\mathbb F_q\) be the finite field of \(q\) elements and characteristic \(p > 3\), and \(\bar{\mathbb F}_q\) its algebraic closure. Let \(\ell\) be a prime with \(\ell \neq p\). The isogeny graph \(\mathcal{H}(\bar{\mathbb F}_q)\) is a directed graph whose vertices are the \(\bar{\mathbb F}_q\)-isomorphism classes of elliptic curves defined over \(\mathbb F_q\), and whose directed arcs represent \(\mathbb F_q\)-isogenies of degree \(\ell\) between elliptic curves in the isomorphism classes. The subgraph \(\mathcal{G}_{\ell}(\bar{\mathbb F}_{p^2})\) of \(\mathcal{H}(\bar{\mathbb F}_{p^2})\) induced by the vertices corresponding to isomorphism classes of supersingular elliptic curves over \(\mathbb F_{p^2}\) is that is an expander graph. This property was used for the construction of some signature schemes and hash functions. In this paper, the authors investigate the supersingular isogeny graph \(\mathcal{G}(\mathbb F_{p^2})\) whose vertices are representatives of the \(\mathbb F_{p^2}\)-isomorphism classes of supersingular elliptic curves defined over \(\mathbb F_{p^2}\) and whose directed arcs represent \( \mathbb F_{p^2}\)-isogenies of degree \(\ell\) between the elliptic curves. More precisely, the three small subgraphs of \(G_{\ell}(\mathbb F_{p^2})\) whose vertices correspond to supersingular elliptic curves \(E\) over \(\mathbb F_{p^2}\) with \(t = p^2 + 1 - \# E(\mathbb F_{p^2}) \in \{0, -p, p\}\) are completely described, and the two large subgraphs of \(G_{\ell}(\mathbb F_{p^2})\) whose vertices correspond to supersingular elliptic curves \(E\) over \(\mathbb F_{p^2}\) with \(t = p^2 + 1 -\#E(\mathbb F_{p^2}) \in \{-2p, 2p\}\) are studied. Furthermore, some observations about the number of loops at the vertices corresponding to elliptic curves with \(j\)-invariant equal to 0 or 1728 are given.