Computing a Basis of the Set of Isogenies Between Two Supersingular Elliptic Curves

Let \(E, E'\) be two supersingular elliptic curves defined over a finite field. The set \(\textrm{Hom}(E, E')\) of isogenies from E to \(E'\) forms a free \(\mathbb {Z}\) -module of rank 4. We give a way to compute an explicit \(\mathbb {Z}\) -basis of \(\textrm{Hom}(E, E')\) . A key ingredient is finding two isogenies \(\varphi , \psi : E \rightarrow E'\) of coprime degrees, which we can find using the meet-in-the-middle algorithm over two different supersingular isogeny graphs. We then left-compose the isogenies \(\varphi \) and \(\psi \) with endomorphisms of E to obtain generators of \(\textrm{Hom}(E, E')\) . Finally, we remove the \(\mathbb {Z}\) -linear dependency of the generators by linear algebra to get a \(\mathbb {Z}\) -basis of \(\textrm{Hom}(E, E')\) .