Pairing the volcano

Abstract. Isogeny volcanoes are graphs whose vertices are elliptic curves and whose edges are `-isogenies. Algorithms allowing to travel on these graphs were developed by Kohel in his thesis (1996) and later on, by Fou-quet and Morain (2001). However, up to now, no method was known, to predict, before taking a step on the volcano, the direction of this step. Hence, in Kohel's and Fouquet-Morain algorithms, we take many steps before choosing the right direction. In particular, ascending or horizon-tal isogenies are usually found using a trial-and-error approach. In this paper, we propose an alternative method that efficiently finds all points P of order ` such that the subgroup generated by P is the kernel of an horizontal or an ascending isogeny. In many cases, our method is faster than previous methods.