The Supersingular Isogeny Problem in Time and Memory $p^{1/3+o(1)}$, Unconditionally
An unconditional algorithm solves the supersingular isogeny problem in p to the 1/3-plus-little-o time and memory.
The paper gives an unconditional Las Vegas algorithm for the supersingular OneEnd problem: finding a non-scalar endomorphism of a supersingular elliptic curve over the field with p squared elements. Known reductions mean the algorithm also solves the supersingular endomorphism-ring and isogeny problems. Expected time and memory are p to the 1/3 times a subexponential factor, equivalently p to the 1/3 plus little-o of 1, improving the previous unconditional exponent of 2/5 without a smoothness heuristic. It uses predetermined smooth degrees, random-walk collisions, split-degree list matching, and composition with Frobenius.
- Solving OneEnd also solves endomorphism-ring and supersingular isogeny problems.
- Expected time and memory are p to the 1/3 plus little-o of 1.
- The result improves the prior unconditional exponent of 2/5.
- No smoothness heuristic is required for the Las Vegas analysis.
Full article165 words · extracted from arxiv.org · click to collapse
Given a supersingular elliptic curve $E/\mathbb{F}_{p^2}$, the $\mathsf{OneEnd}$ problem asks for a non-scalar endomorphism of $E$. By known reductions, solving this problem also solves the supersingular endomorphism ring and isogeny problems. Wesolowski obtained exponent $1/3$ under an assumption on the factorization of a small degree, whereas the previous unconditional exponent was $2/5$. 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.
Text extracted automatically; images, tables and formatting may be missing. Original: https://arxiv.org/abs/2609.22018