Finding a Basis of the Set of Isogenies between Two Ordinary Elliptic Curves Over a Finite Field

Let E, E ′ be two isogenous ordinary elliptic curves defined over a finite field. The set Hom( E, E ′) of isogenies from E to E ′ is a free ℤ-module of rank two. In this paper, we give an algorithm for finding an explicit ℤ-basis of Hom( E, E ′). Firstly, we find a special pair of isogenies using the structure of ordinary isogeny graphs, called isogeny volcanoes. Secondly, we construct explicit generators of Hom( E, E ′) as a ℤ-module from the pair of isogenies. Finally, we remove the ℤ-linear dependency of the generators to obtain a ℤ-basis of Hom( E,E ′).