Computing supersingular endomorphism rings using inseparable endomorphisms

arXiv2306.03051MaRDI QIDQ6439280FDOQ6439280

Authors: Jenny G. Fuselier, Annamaria Iezzi, Mark Kozek, Travis Morrison, Changningphaabi Namoijam 

Publication date: 5 June 2023

Abstract: We give an algorithm for computing inseparable endomorphisms of a supersingular elliptic curve $E$ defined over $mathbb{F}_{p^2}$, which, conditional on GRH, runs in expected $O(sqrtp(logp{)}^2(loglogp{)}^3)$ time. With two calls to this algorithm, we compute a Bass suborder of $extEnd(E)$, improving on the results of Eisentr"{a}ger, Hallgren, Leonardi, Morrison, and Park (ANTSXIV) who only gave a heuristic algorithm for computing a Bass suborder. We further improve on the results of Eisentr"{a}ger et al. by removing the heuristics involved in an algorithm for recovering $extEnd(E)$ from a Bass suborder. We conclude with an argument that $O(1)$ endomorphisms generated by our algorithm along with negligible overhead suffice to compute $extEnd(E)$, conditional on a heuristic assumption about the distribution of the discriminants of these endomorphisms.

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16)

This page was built for publication: Computing supersingular endomorphism rings using inseparable endomorphisms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6439280)