Orienteering with one endomorphism (Q6093270)

Let \(p\)\, be a prime number and \(E,\, E_{init}\)\, two supersingular curves, defined over \(\mathbf{F}_{p^2}\),\, in a \(l\)-isogeny graph (\(l\)\, prime, \(l\ne p)\). The path-finding problem asks to find a path (a chain of \(l\)-isogenies) between \(E\)\, and \(E_{init}\). Here the paper takes as initial curve \(E_{init}\)\, the elliptic curve with j-invariant j=1728. The path-finding problem is a hard problem, equivalent to the endomorphism problem (to find the ring End\((E)\)), see [\textit{K. Eisenträger} et al., Lect. Notes Comput. Sci. 10822, 329--368 (2018; Zbl 1415.94426)]. The present paper, given an explicit endomorphism \(\theta\)\, of \(E\)\, provides algorithms for solving the path-finding problem for \(E,E_{init}\). Let us remember that the endomorphism \(\theta\)\, provides an orientation of the elliptic curve \(E\)\, and then the graph of oriented supersingular curves has a volcano structure, similar to the case of ordinary elliptic curve, see [\textit{D. R. Kohel}, Endomorphism rings of elliptic curves over finite fields. Berkeley: University of California (PhD Thesis) (1996)] and that structure is used in the paper. The algorithms are assure by Theorems 1.1 and 1.2, stated in Section 1 and proved in Section 11. They rely on several heuristic assumptions and need many other auxiliary results and algorithms, see 1.2 and 1.3 and Sections 2 to 10. The first algorithm is a classical one and has computational complexity \(h_{\Delta'}L_d(1/2)\mathrm{poly}(\log p)\),\, where \(d\)\, is the degree of \(\theta\),\, \(\Delta'\)\, the \(l\)-fundamental part of the discriminant \(\Delta\)\, of \(\theta\)\, and \(h_{\Delta'}\)\, the class number of the quadratic order of discriminant \(\Delta'\). The second algorithm is a quantum algorithm and has runtime subexponential in \(\log|\Delta|\)\, and polynomial in \(\log p\).