Connecting Kani's Lemma and path-finding in the Bruhat-Tits tree to compute supersingular endomorphism rings

2024/02/07 by Kirsten Eisentraeger, Eisentraeger, Kirsten, Gabrielle Scullard +1
Computer Science · Mathematics · #11G20 #11R52 #11Y16 #14K02 #Algebraic Geometry and Number Theory #Cellular Automata and Applications #Coding theory and cryptography #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #FOS: Mathematics #Number Theory (math.NT)

paper · pdf · doi:10.48550/arxiv.2402.05059

openalex publication_date 2024/02/07 · openalex created_date 2024/02/09 · openalex updated_date 2026/07/28

Abstract

We give a deterministic polynomial time algorithm to compute the endomorphism ring of a supersingular elliptic curve in characteristic p, provided that we are given two noncommuting endomorphisms and the factorization of the discriminant of the ring O₀ they generate. At each prime q for which O₀ is not maximal, we compute the endomorphism ring locally by computing a q-maximal order containing it and, when q ≠ p, recovering a path to End(E) ⊗ ℤ_q in the Bruhat-Tits tree. We use techniques of higher-dimensional isogenies to navigate towards the local endomorphism ring. Our algorithm improves on a previous algorithm which requires a restricted input and runs in subexponential time under certain heuristics. Page and Wesolowski give a probabilistic polynomial time algorithm to compute the endomorphism ring on input of a single non-scalar endomorphism. Beyond using techniques of higher-dimensional isogenies to divide endomorphisms by a scalar, our methods are completely different.

Related

• Computing endomorphism rings of supersingular elliptic curves and connections to pathfinding in isogeny graphs
• The supersingular endomorphism ring problem given one endomorphism
• The supersingular Endomorphism Ring and One Endomorphism problems are equivalent
• Orienteering with one endomorphism
• The supersingular isogeny path and endomorphism ring problems are\n equivalent