Computing isogenies between supersingular elliptic curves over \(\mathbb {F}_p\) (Q5963365): Difference between revisions

In this article, the authors consider the problem of constructing an isogeny between two supersingular elliptic curves defined over \(\mathbb{F}_p\) (\(p>3\)). The fastest known algorithm to do this solves the problem in the isogeny graph of cardinality \(O(p)\) of all supersingular curves over \({\mathbb{F}}_{p^2}\) using a meet-in-the-middle search and runs in \(\tilde{O}(p^{1/2})\) (the notation \(\tilde{O}\) means forgetting about logarithmic factors). The present idea is to use the fact that both curves are defined over \(\mathbb{F}_p\) to find a path in a graph which looks more like the ordinary case graph and which has only \(\tilde{O}(p^{1/2})\) elements, hence a complexity of \(\tilde{O}(p^{1/4})\). In order to provide the algorithm, the authors rely on the classical results of [\textit{W. C. Waterhouse}, Ann. Sci. Éc. Norm. Supér. (4) 2, 521--560 (1969; Zbl 0188.53001)] to derive the structure of the graph, in particular a minimal set of isogeny degrees which make the graph connected.