🔢 mathematics

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

This paper presents a deterministic polynomial-time algorithm for computing the endomorphism ring of a supersingular elliptic curve given two noncommuting endomorphisms and the factorization of their generated ring's discriminant, by leveraging Kani's Lemma, higher-dimensional isogenies, and path-finding in the Bruhat-Tits tree to improve upon previous subexponential and probabilistic methods.

Original authors: Kirsten Eisentraeger, Gabrielle Scullard

Published 2026-01-22

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Kirsten Eisentraeger, Gabrielle Scullard

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a massive, intricate jigsaw puzzle. The picture you are trying to complete is the Endomorphism Ring of a special type of mathematical object called a supersingular elliptic curve.

In the world of cryptography (specifically, the kind that might survive quantum computers), knowing the exact shape of this puzzle is crucial. If you don't know the full picture, the system is secure. If you can figure it out, you might be able to break the code.

For a long time, finding this full picture was like trying to find a needle in a haystack while blindfolded. You might find a few pieces (some mathematical functions called "endomorphisms"), but you didn't know how they fit together to form the complete structure.

Here is what Kirsten Eisenträger and Gabrielle Scullard have done in this paper, explained through simple analogies:

1. The Starting Point: A Few Puzzle Pieces

The researchers start with a "sub-order." Think of this as having a small, incomplete cluster of puzzle pieces that you know belong to the big picture. You have two specific pieces that don't quite fit together in a simple way (they "don't commute"), and you know the "discriminant" (a mathematical measurement of how incomplete your cluster is).

2. The Map: The Bruhat-Tits Tree

To find the missing pieces, the authors use a map called the Bruhat-Tits tree.

The Analogy: Imagine a giant, infinite family tree or a subway map where every station represents a possible version of your puzzle.
The Goal: Your current incomplete puzzle is at one station. The "perfect" puzzle (the Endomorphism Ring) is at another station somewhere down the line.
The Problem: The map is huge. You can't just walk down every path to find the right one; it would take too long.

3. The New Tools: Kani's Lemma and Higher Dimensions

The paper introduces two main "superpowers" to navigate this map efficiently:

The "Magic Divider" (Division Algorithm):
Imagine you have a complex machine (an endomorphism) and you want to know if it can be split into smaller, simpler machines. The authors use a technique involving higher-dimensional isogenies (which is like temporarily lifting your 2D puzzle into 3D space). In this 3D space, it's much easier to see if a piece can be cleanly divided. If it can, you know you are on the right track. This is based on Kani's Lemma, a mathematical rule that allows moving problems between different dimensions.
The "Intersection Detector" (Tu's Theorem):
Imagine you are looking for a specific room in a building. Instead of checking every single room, you check the intersection of three different hallways. If a room exists where all three hallways meet, you know exactly where to look. The authors use a theorem by Tu to show that they can rule out huge sections of the "map" (the tree) by checking just a few specific intersections. This lets them eliminate thousands of wrong paths instantly.

4. The Strategy: Local vs. Global

The algorithm works by solving the problem locally first, then putting it all together.

Local: They look at the puzzle through a "microscope" at specific prime numbers (like looking at the puzzle under a specific colored light). At each prime, they figure out exactly how far they are from the perfect solution on the map.
The Path: They don't just guess. They use a binary search (like guessing a number between 1 and 100 by asking "is it higher or lower?") to walk down the tree step-by-step until they hit the exact station where the perfect puzzle lives.
Global: Once they have the perfect local pieces for every prime number, they stitch them together to form the complete, global Endomorphism Ring.

5. Why This Matters

Before this paper, finding this ring was slow and often relied on luck (probabilistic methods) or required very specific, rare starting conditions.

The Breakthrough: This new method is deterministic (it always works, no guessing) and polynomial time (it scales reasonably well as the numbers get bigger).
The Result: They can now take a partial set of puzzle pieces and mathematically guarantee they can build the whole picture, provided they have the factorization of the "discriminant" (the measure of incompleteness).

Summary

Think of the paper as providing a GPS and a set of high-tech tools for a traveler lost in a giant, confusing forest (the mathematical world of elliptic curves).

Old way: Wander aimlessly, hoping to stumble upon the exit.
New way: Use a map (the tree), a magic compass (Kani's Lemma) to check directions, and a laser scanner (intersection theorems) to instantly see which paths lead to dead ends.

The authors have created a reliable, fast, and guaranteed method to reconstruct the full "Endomorphism Ring" from just a few starting clues. This is a significant step forward for understanding the security of future encryption systems.

Technical Summary: Connecting Kani's Lemma and Path-Finding in the Bruhat-Tits Tree to Compute Supersingular Endomorphism Rings

Problem Statement
The fundamental problem addressed is the deterministic computation of the endomorphism ring, $\text{End}(E)$ , of a supersingular elliptic curve $E$ defined over $\mathbb{F}_{p^2}$ . While computing the endomorphism ring of ordinary curves has seen recent polynomial-time advances (under GRH and factoring oracles), the supersingular case remains challenging. Previous approaches, such as Kohel's cycle-finding algorithm, run in $O(p^{1+\epsilon})$ time. More recent subexponential algorithms (e.g., [EHL+20]) rely on heuristics and require the input order to be a Bass order. Furthermore, probabilistic polynomial-time reductions exist (e.g., [PW24]) between finding a single non-scalar endomorphism and the full ring, but deterministic methods with restricted inputs have been limited.

This paper aims to provide a deterministic polynomial-time algorithm to compute $\text{End}(E)$ given:

The curve $E$ .
Two non-commuting endomorphisms $\alpha_1, \alpha_2$ generating a suborder $O_0 \subset \text{End}(E)$ .
The factorization of the reduced discriminant $\Delta$ of $O_0$ .

The algorithm's complexity is polynomial in $\log p$ , the degrees of the input endomorphisms, and the largest prime factor of $\Delta/p$ .

Methodology
The authors leverage the local-global principle for quaternion algebras. Since $\text{End}(E)$ is a maximal order in the quaternion algebra $B_{p,\infty}$ (ramified at $p$ and $\infty$ ), determining $\text{End}(E)$ globally is equivalent to determining its local completions $\text{End}(E) \otimes \mathbb{Z}_q$ at every prime $q$ dividing the reduced discriminant of $O_0$ .

The methodology proceeds in two main phases for each prime $q \neq p$ where $O_0$ is not maximal:

Local Enlargement and Embedding:
- The algorithm constructs a $q$ -maximal $q$ -enlargement $O_q$ of $O_0$ (an order maximal at $q$ but equal to $O_0$ elsewhere).
- Using techniques from Voight, an isomorphism $f: O_q \otimes \mathbb{Z}_q \to M_2(\mathbb{Z}_q)$ is computed, mapping the local order to the root of the Bruhat-Tits tree for $GL_2(\mathbb{Q}_q)$ .
- The target $\Lambda_E = f(\text{End}(E) \otimes \mathbb{Z}_q)$ is a vertex in this tree. The goal is to find the path from the root to $\Lambda_E$ .
Path-Finding in the Bruhat-Tits Tree:
- Distance Computation: The algorithm first determines the distance $r$ between the root and $\Lambda_E$ . This is done by finding the smallest integer $r$ such that $q^r O_q \subset \text{End}(E)$ . This relies on a division algorithm (Proposition 2.7) that tests if a rational multiple of an endomorphism is integral.
- Path Recovery: Once $r$ $r$ is known, the algorithm recovers the specific path (sequence of matrices) to $\Lambda_E$ $Λ_{E}$ .
  - General Case: It tests candidates step-by-step. For a path of length $k$ , it constructs a global order corresponding to the intersection of maximal orders along a candidate path. It then uses the division algorithm to check if this global order is contained in $\text{End}(E)$ . If yes, the path continues; if no, that branch is pruned. This utilizes the fact that the intersection of finitely many maximal orders can be reduced to the intersection of at most three (Tu's Theorem).
  - Bass Case: If $O_0$ is a Bass order at $q$ , the maximal orders containing it form a simple path in the tree. The algorithm performs a binary search along this path to locate $\text{End}(E) \otimes \mathbb{Z}_q$ efficiently.
Global Reconstruction:
- Once the local maximal orders $\tilde{O}_q$ are identified for all relevant $q$ , they are combined with the original order $O_0$ to form the global maximal order $\text{End}(E)$ .

Key Technical Tools

Kani's Lemma and Higher-Dimensional Isogenies: The core engine for the division algorithm (Proposition 2.7) is Kani's Lemma. This allows the translation of the problem of dividing an endomorphism by an integer into a higher-dimensional setting (isogenies between products of elliptic curves). This flexibility enables the imposition of powersmoothness conditions necessary for efficient evaluation, a technique previously used in [Rob22] and [PW24] but applied here deterministically to navigate the Bruhat-Tits tree.
Tu's Theorem on Intersections: The paper utilizes a theorem by Tu [Tu11] stating that the intersection of any finite set of maximal orders in $M_2(\mathbb{Q}_q)$ is equal to the intersection of at most three of them. This allows the algorithm to test the containment of complex intersections of local orders by constructing corresponding global orders and testing them against $\text{End}(E)$ , effectively ruling out large sets of candidates simultaneously.
HD Representation: Endomorphisms are represented using "HD representation" (images on torsion points), which allows for efficient evaluation and degree analysis, crucial for the polynomial-time runtime.

Results and Complexity
The paper presents Theorem 1.1, stating the existence of an algorithm that computes $\text{End}(E)$ in deterministic polynomial time relative to $\log p$ , the input degrees, and the factorization of the discriminant.

General Case: The complexity is linear in the number of primes dividing $\Delta/p$ and the largest such prime. The number of calls to the division algorithm is bounded by $4(e_q + 2)$ per prime $q$ , where $e_q = v_q(\text{discrd}(O_0))$ .
Bass Case: If the input order is Bass at $q$ , the complexity improves to $4 \log_2(e_q + 1)$ calls to the division algorithm via binary search.
Comparison: This improves upon [EHL+20], which required the Bass restriction and relied on heuristics, running in subexponential time. It also differs from [PW24] by being deterministic and not requiring an oracle for non-scalar endomorphisms, though it assumes the input factorization.

Significance and Claims
The authors claim this work completes Kohel's approach of generating a subring and extending it to the full ring, providing a deterministic solution where previous methods were either heuristic or probabilistic.

Cryptographic Relevance: The computation of supersingular endomorphism rings is central to the security of isogeny-based cryptosystems (e.g., SIDH, which was broken in 2022). The hardness of this problem is a necessary condition for the security of such schemes.
Methodological Advancement: The paper demonstrates that techniques involving higher-dimensional isogenies (via Kani's Lemma), originally developed for breaking SIDH and computing ordinary endomorphism rings, can be effectively repurposed to navigate the structure of the Bruhat-Tits tree for supersingular curves.
Generality: Unlike previous algorithms that required the input order to be Bass, this method works for general orders, offering a more robust tool for analyzing supersingular endomorphism rings.

The paper concludes by providing a concrete example with $p=103$ , illustrating the step-by-step process of enlarging the order, computing distances, and recovering the path in the Bruhat-Tits tree to reconstruct the full endomorphism ring.