The Supersingular Isogeny Problem in Time and Memory , Unconditionally
In the authors' words
Given a supersingular elliptic curve , the problem asks for a non-scalar endomorphism of . By known reductions, solving this problem also solves the supersingular endomorphism ring and isogeny problems. Wesolowski obtained exponent under an assumption on the factorization of a small degree, whereas the previous unconditional exponent was . We give a Las Vegas algorithm, analyzed without a smoothness heuristic, with expected time and memory \[ p^{1/3}\exp\bigl(O(\sqrt{\log p \log\log p})\bigr) = p^{1/3+o(1)}. \] The algorithm fixes in advance a family of degrees that are products of small primes. Known counting results provide many isogenies of these degrees from curves to their Frobenius conjugates, and a collision estimate shows that the isogenies occur on sufficiently many distinct curves for a random walk to reach one of them. From such a curve, the algorithm splits a degree into two parts, enumerates two lists of shorter isogenies, and matches their targets to obtain an isogeny to the conjugate, whose composition with Frobenius gives the required endomorphism.
Appeared: Monday, September 21. arXiv. Preprint, not yet peer-reviewed.