The Supersingular Isogeny Problem in Time and Memory , Unconditionally
En palabras de los autores
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.
Apareció: lunes, 21 de septiembre. arXiv. Preprint, todavía sin revisión por pares.