Computing endomorphism rings of supersingular elliptic curves and connections to pathfinding in isogeny graphs

Kirsten Eisenträger (Pennsylvania State), Sean Hallgren (Pennsylvania State), Chris Leonardi (University of Waterloo), Travis Morrison (Pennsylvania State), and Jennifer Park (University of Michigan)

29-Jun-2020, 21:45-22:15 (4 years ago)

Abstract: Computing endomorphism rings of supersingular elliptic curves is an important problem in computational number theory, and it is also closely connected to the security of some of the recently proposed isogeny-based cryptosystems. In this paper we give a new algorithm for computing the endomorphism ring of a supersingular elliptic curve $E$ that runs, under certain heuristics, in time $O((\log p)^2p^{1/2})$. The algorithm works by first finding two cycles of a certain form in the supersingular $\ell$-isogeny graph $G(p,\ell)$, generating an order $\Lambda \subseteq \mathrm{End}(E)$. Then all maximal orders containing $\Lambda$ are computed, extending work of Voight. The final step is to determine which of these maximal orders is the endomorphism ring. As part of the cycle finding algorithm, we give a lower bound on the set of all $j$-invariants $j$ that are adjacent to $j^p$ in $G(p,\ell)$, answering a question in arXiv:1909.07779.

cryptography and securityalgebraic geometrynumber theory

Audience: researchers in the topic

( chat | paper | slides | video )

Comments: The slides used in the pre-recorded video can be found here.

Chairs: Steven Galbraith and Christophe Petit


Algorithmic Number Theory Symposium (ANTS XIV)

Series comments: Registration is now open. Registration is free but required to access the chat and livestream.

This is a hybrid synchronous/asynchronous conference with several ways to participate.

  • Click the "paper" link to view contributed papers and posters (open to all).
  • Click the "video" link to view pre-recorded talks of accepted papers (open to all).
    These are 15-20 minutes aimed at a general algorithmic number theory audience.
  • Click the "slides" link to view slides used in the pre-recorded video when available (open to all).
  • Click the "chat" link to access the chat stream related to the talk or poster before, during, and after the live event (registration required).
  • Click the "livestream" button to join the live event when it is taking place (registration required and you must be logged in).
    For accepted papers the audience will be expected to have watched the pre-recorded video and have the paper in front of them.

The invited talks will be recorded and made available via the "video" link after the talk is over. None of the other sessions will be recorded.

Organizer: Steven Galbraith*
Curator: Andrew Sutherland*
*contact for this listing

Export talk to