🔢 mathematics

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

本文提出了一种确定性多项式时间算法，用于在给定两个非交换自同态及其生成的环的判别式分解的情况下，计算超奇异椭圆曲线的自同态环，该算法通过利用 Kani 引理、高维同源以及在 Bruhat-Tits 树中的路径查找，改进了以往的亚指数和概率方法。

原作者： Kirsten Eisentraeger, Gabrielle Scullard

发布于 2026-01-22

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： Kirsten Eisentraeger, Gabrielle Scullard

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正在试图解决一个巨大且复杂的拼图。你试图完成的图像是某种特殊数学对象的自同态环（Endomorphism Ring）——即超奇异椭圆曲线（supersingular elliptic curve）。

在密码学世界中（特别是那种能够抵御量子计算机攻击的密码学），了解这个拼图的精确形状至关重要。如果你不知道完整的图像，系统就是安全的；如果你能破解出它的全貌，你就能破解代码。

长期以来，寻找这个完整图像的过程就像是在蒙着眼睛于草堆中寻找一根针。你可能会找到一些碎片（被称为“自同同态”的数学函数），但你并不知道它们如何组合在一起形成完整的结构。

以下是 Kirsten Eisenträger 和 Gabrielle Scullard 在这篇论文中所做的工作，通过简单的类比进行解释：

1. 起点：少量的拼图碎片

研究人员从一个“子阶（sub-order）”开始。你可以把它想象成拥有一个已知属于大图景的一小簇不完整的拼图碎片。你拥有两个特定的碎片，它们无法以简单的方式组合在一起（它们“不对易”），并且你知道“判别式（discriminant）”（一个衡量你的集群有多不完整的数学度量）。

2. 地图：布鲁阿-蒂茨树（Bruhat-Tits Tree）

为了找到缺失的碎片，作者使用了一张名为布鲁阿-蒂茨树的地图。

类比： 想象一个巨大的、无限的家族树或地铁路线图，每一个站点都代表你拼图的一个可能版本。
目标： 你当前的不完整拼图位于一个站点。而那个“完美的”拼图（自同态环）位于这条线路上另一处的某个站点。
问题： 这张地图非常庞大。你不能沿着每条路径走遍所有路，否则会耗费太长时间。

3. 新工具：Kani 引理与高维空间

论文引入了两种主要的“超能力”，用于高效地在这张地图上导航：

“神奇除法器”（Division Algorithm）：
想象你有一个复杂的机器（一个自同态），你想知道它是否可以被拆解成更小、更简单的机器。作者使用了一种涉及**高维同源（higher-dimensional isogenies）**的技术（这就像是暂时将你的二维拼图提升到三维空间）。在三维空间中，更容易看出一个碎片是否可以被整齐地分割。如果它可以，你就知道自己正处于正确的轨道上。这基于 Kani 引理，该引理是一个允许在不同维度之间转移问题的数学规则。
“交集探测器”（Intersection Detector）：
想象你正在寻找一栋建筑中的特定房间。与其检查每一个房间，不如检查三个不同走廊的交汇处。如果三个走廊相交的地方确实存在一个房间，你就知道确切的寻找位置。作者利用 Tu 的定理来展示，他们可以通过检查几个特定的交点，就能排除掉地图（树）中的大部分区域。这让他们能够瞬间排除掉成千上万条错误的路径。

4. 策略：局部与全局

该算法通过先解决局部问题，然后再将其整合起来的方式运行。

局部： 他们通过特定的素数（就像是在特定的彩色光线下观察拼图）通过“显微镜”观察拼图。在每个素数下，他们确定了自己在地图上距离完美解还有多远。
路径： 他们不是在瞎猜。他们使用二分查找（类似于通过询问“是更高还是更低”来猜测 1 到 100 之间的数字）在树上一步步行走，直到到达那个完美拼图所在的精确站点。
全局： 一旦他们获得了每个素数的完美局部碎片，他们就会将它们缝合在一起，形成完整的全局自同态环。

5. 为什么这很重要

在这篇论文发表之前，寻找这个环是非常缓慢的，且往往依赖于运气（概率方法），或者需要非常特定且罕见的起始条件。

突破点： 这种新方法是确定性的（总是有效，无需猜测）且是多项式时间的（随着数字变大，其规模增长仍处于合理范围内）。
结果： 只要拥有“判别式”（不完整程度的度量）的因数分解，他们现在就可以从仅有的少量起始线索出发，在数学上保证能够构建出完整的自同态环。

总结

你可以将这篇论文看作是为一名迷失在巨大且混乱森林（椭圆曲线的数学世界）中的旅行者提供了一份 GPS 和一套高科技工具。

旧方法： 漫无目的地游荡，希望偶然撞见出口。
新方法： 使用地图（树）、使用神奇指南针（Kani 引理）来检查方向，以及使用激光扫描仪（交集定理）来瞬间识别哪些路径是死胡同。

作者创造了一种可靠、快速且有保证的方法，能够仅凭少量的初始线索就重建完整的“自同态环”。这是理解未来加密系统安全性方面迈出的重要一步。

技术摘要：连接 Kani 引理与 Bruhat-Tits 树中的路径查找以计算超奇异端同态环

问题陈述
所解决的核心问题是确定性地计算定义在 $\mathbb{F}_{p^2}$ 上的超奇异椭圆曲线 $E$ 的端同态环 $\text{End}(E)$ 。虽然计算普通曲线的端同态环在近期已取得了多项式时间内的进展（在 GRH 及存在分解预言的情况下），但超奇异情形仍然具有挑战性。以往的方法（如 Kohel 的循环查找算法）运行时间为 $O(p^{1+\epsilon})$ 。更近期的亚指数算法（例如 [EHL+20]）依赖于启发式方法，并且要求输入阶为 Bass 阶。此外，存在概率多项式时间归约（例如 [PW24]）可以在寻找单个非标量端同态与完整环之间建立联系，但具有限制输入的确定性方法一直很有限。

本文旨在提供一个确定性多项式时间算法，用于在给定以下条件时计算 $\text{End}(E)$ ：

曲线 $E$ 。
生成子阶 $O_0 \subset \text{End}(E)$ 的两个非交换端同态 $\alpha_1, \alpha_2$ 。
$O_0$ 的缩减判别式 $\Delta$ 的因子分解。

该算法的复杂度相对于 $\log p$ 、输入端同态的次数以及 $\Delta/p$ 的最大素因子是多项式级的。

方法论
作者利用了四元数代数的局部-全局原理。由于 $\text{End}(E)$ 是四元数代数 $B_{p,\infty}$ （在 $p$ 和 $\infty$ 处分歧）中的极大阶，确定 $\text{End}(E)$ 在全局上等价于确定其在每个整除 $O_0$ 缩减判别式的素数 $q$ 处的局部完备化 $\text{End}(E) \otimes \mathbb{Z}_q$ 。

该方法论针对每个 $O_0$ 在 $q$ 处不是极大的素数 $q \neq p$ ，分为两个主要阶段：

局部扩张与嵌入：
- 算法构造一个 $O_0$ 的 $q$ -极大 $q$ -扩张 $O_q$ （在 $q$ 处极大但在其他地方与 $O_0$ 相等）。
- 利用来自 Voight 的技术，计算一个同构 $f: O_q \otimes \mathbb{Z}_q \to M_2(\mathbb{Z}_q)$ ，将局部阶映射到 $GL_2(\mathbb{Q}_q)$ 的 Bruhat-Tits 树 的根节点。
- 目标 $\Lambda_E = f(\text{End}(E) \otimes \mathbb{Z}_q)$ 是该树中的一个顶点。目标是找到从根到 $\Lambda_E$ 的路径。
Bruhat-Tits 树中的路径查找：
- 距离计算： 算法首先确定根与 $\Lambda_E$ 之间的距离 $r$ 。这是通过寻找最小整数 $r$ ，使得 $q^r O_q \subset \text{End}(E)$ 来实现的。这依赖于一个除法算法（命题 2.7），该算法测试一个端同态的有理倍数是否是整型的。
- 路径恢复： 一旦已知 $r$ $r$ ，算法便恢复到 $\Lambda_E$ $Λ_{E}$ 的特定路径（矩阵序列）。
  - 一般情况： 它逐步测试候选者。对于长度为 $k$ 的路径，它构造一个对应于沿候选路径的极大阶交集的全局阶。然后，它使用除法算法来检查该全局阶是否包含在 $\text{End}(E)$ 中。如果是，则路径继续；如果不是，则剪枝该分支。这利用了有限个极大阶的交集可以简化为至多三个极大阶交集的特性（Tu 定理）。
  - Bass 情况： 如果 $O_0$ 在 $q$ 处是 Bass 阶，则包含它的极大阶在树中形成一条简单的路径。算法通过在该路径上进行二分查找来高效定位 $\text{End}(E) \otimes \mathbb{Z}_q$ 。
全局重构：
- 一旦识别出所有相关 $q$ 的局部极大阶 $\tilde{O}_q$ ，将它们与原始阶 $O_0$ 结合，以形成全局极大阶 $\text{End}(E)$ 。

关键技术工具

Kani 引理与高维同源： 除法算法（命题 2.7）的核心引擎是 Kani 引理。它允许将“将端同态除以一个整数”的问题转化为高维设置（即椭圆曲线乘积之间的同源）。这种灵活性使得能够施加幂光滑条件进行高效评估，这是 [Rob22] 和 [PW24] 中使用的技术，但在此处被用于确定性地导航 Bruhat-Tits 树。
Tu 关于交集的定理： 文中利用了 Tu [Tu11] 的定理，该定理指出 $M_2(\mathbb{Q}_q)$ 中任何有限个极大阶的交集等于其中至多三个极大阶的交集。这使得算法可以通过构造相应的全局阶并测试其是否包含在 $\text{End}(E)$ 中，来测试复杂交集的包含性，从而有效地同时排除大量的候选集合。
HD 表示： 端同态使用“HD 表示”（在挠点上的像）进行表示，这允许高效的评估和次数分析，对于实现多项式时间复杂度至关重要。

结果与复杂度
论文提出了 定理 1.1，声明存在一个确定性多项式时间算法，相对于 $\log p$ 、输入次数以及判别式的因子分解来计算 $\text{End}(E)$ 。

一般情况： 复杂度相对于整除 $\Delta/p$ 的素数个数及最大的此类素数是线性的。每个素数 $q$ 调用除法算法的次数由 $4(e_q + 2)$ 限制，其中 $e_q = v_q(\text{discrd}(O_0))$ 。
Bass 情况： 如果输入阶在 $q$ 处是 Bass 阶，通过二分查找，复杂度优化为 $4 \log_2(e_q + 1)$ 次除法算法调用。
对比： 这改进了 [EHL+20]，后者需要 Bass 限制并依赖启发式方法，运行时间为亚指数级。它也不同于 [PW24]，因为它是确定性的，且不需要非标量端同态的预言机，尽管它假设了输入已分解。

意义与主张
作者声称这项工作完成了 Kohel 的方法——即生成一个子环并将其扩展到完整环——提供了一个确定性的解决方案，而以往的方法要么是启发式的，要么是概率性的。

密码学相关性： 计算超奇异端同态环的计算对于基于同源的密码体制（例如在 2022 年被破解的 SIDH）的安全性至关重要。端同态环计算的难度是这些方案安全性的必要条件。
方法论进步： 论文展示了涉及高维同源（通过 Kani 引理）的技术——最初用于破解 SIDH 和计算普通端同态环——如何被有效地重新利用，以导航超奇异曲线的 Bruhat-Tits 树。
通用性： 不同于以往要求输入阶为 Bass 阶的算法，此方法适用于一般阶，为分析超奇异端同态环提供了更鲁棒的工具。

论文最后通过一个 $p=103$ 的具体示例进行了总结，展示了扩大阶、计算距离以及在 Bruhat-Tits 树中恢复路径以重构完整端同态环的逐步过程。

1. 起点：少量的拼图碎片

2. 地图：布鲁阿-蒂茨树（Bruhat-Tits Tree）

3. 新工具：Kani 引理与高维空间

4. 策略：局部与全局

5. 为什么这很重要

总结

类似论文