The Spine: A Supersingular Highway

技术摘要：脊柱（The Spine）：一条超奇异高速公路

问题陈述
本文旨在对有限域 $\mathbb{F}_p$ 上超奇异 $\ell$-同构图的“脊柱”（$Sp_\ell$）进行结构特征化。脊柱被定义为全同构图 $G_\ell(\mathbb{F}_p)$ 的子图，其顶点（椭圆曲线）的 $j$-不变元均定义在 $\mathbb{F}_p$ 上。虽然之前的研究（特别是 [HAS26]）针对许多 $p$ 和 $\ell$ 的同余条件提供了 $Sp_\ell$ 的显式图论描述，但仍留下了一个特定的未解决情况：$\ell=2$ 且 $p \equiv 71, 119 \pmod{120}$。

在这种特定情况下，从全图 $G_\ell(\mathbb{F}_p)$ 到脊柱 $Sp_\ell$ 的转换涉及一个分量的“折叠”（folding）和另一些分量的“堆叠”（stacking）。至关重要的是，脊柱中增加了一条并非定义在 $\mathbb{F}_p$ 上的新边。尚未解决的问题是确定这条新边是作为“边附着”（edge attachment，连接两个此前不连通的分量）起作用，还是仍然留在单个分量内部。这种区别至关重要，因为边附着会显著改变图的直径和连通性，从而直接影响同构算法中路径查找算法的效率。

方法论
作者结合代数数论和图论来分析 $\ell=2$ 且 $p \equiv 71, 119 \pmod{120}$ 时 $Sp_\ell$ 的结构。

1. 图分解： 本文利用函数 $\Gamma$ 和 $\Theta$（在 [HAS26] 中形式化）来建模从 $G_\ell(\mathbb{F}_p)$ 到 $Sp_\ell$ 的转换。$\Gamma$ 代表将 $\mathbb{F}_{p^2}$-同构类合并为 $\mathbb{F}_p$-同构类（堆叠与折叠），而 $\Theta$ 则增加了非 $\mathbb{F}_p$ 的边。
2. 分量分析： 中间图 $\Gamma(G_\ell(\mathbb{F}_p))$ 的分量被分为两类：
   • 折叠分量 ($F$)： 一个包含 $j$-不变元 1728 和 8000 的树状结构。
   • 堆叠分量 ($T$)： 通过合并同构分量形成的环状结构。
3. 度量推导： 本文推导了 $F$ 和 $T$ 的距离、离心率和直径函数的显式公式。它确立了堆叠分量的直径为 $\frac{1}{2}(\text{ord}(\ell)+3)$，以及折叠分量的直径为 $\frac{1}{2}(\text{ord}(\ell)+1)$，其中 $\text{ord}(\ell)$ 是素数在 $\mathbb{Q}(\sqrt{-p})$ 类群中的阶。
4. 边影响分析： 作者分析了由 $\Theta$ 增加的新边 $E$ 在三种场景下的影响：
   • $E$ 位于一个堆叠分量内部。
   • $E$ 位于折叠分量内部。
   • $E$ 连接两个不同的分量（边附着）。
5. 平均直径启发式： 本文的一个关键方法论贡献是定义了不连通图的“平均直径”。本文证明，当且仅当发生边附着时， $Sp_\ell$ 的平均直径会严格增加。这使得能够根据计算出的平均直径值来区分不同的结构情况。
6. 计算验证： 作者使用卡尔加里大学的 MSX1 服务器，计算了 10,000 个满足同余条件的素数（范围从 17,471 到 2,186,519）的平均直径。这些值被用来与基于类数 $h(-p)$ 和 $\text{ord}(\ell)$ 的理论界限进行比较，从而对每个素数的脊柱结构进行分类。

核心贡献

• 显式直径公式： 本文首次为 $\ell=2, p \equiv 71, 119 \pmod{120}$ 的特定情况提供了折叠分量和堆叠分量的距离、离心率及直径函数的完整推导。
• 通过平均直径进行结构区分： 它建立了一种通过计算脊柱的平均直径来区分边附着与非附着场景的严谨方法。文中提供了一个算法（算法 1），可在给定 $\text{ord}(\ell)$、$h(-p)$ 和平均直径的情况下确定脊柱的结构。
• 经验启发式： 通过广泛的计算，本文提供了关于边附着频率以及新边位置分布的数据驱动启发式结果。

结果
对 10,000 个素数的计算研究得出了以下经验结果：

• 类群生成： 在约 77.93% 的案例中，上方的 2 生成了类群（$h(-p) = \text{ord}(\ell)$）。在这些实例中，脊柱仅由折叠分量组成，且没有发生边附着。
• 边附着频率： 在剩余的 22.07% 的案例中（存在堆叠分量时），约 67.29% 的实例发生了边附着。
• 边位置： 当发生边附着时，涉及折叠分量与涉及两个堆叠分量的附着之间大约呈现对半开的分布。
• 非附着边： 当没有发生附着时，新边很少被发现能减小图的直径（在具有多个分量的案例中约为 3.08%）。
• 分布异常： 数据表明，相比于纯随机分布，新边不太可能作为一条短的、非附着的边出现在折叠分量内。

意义
本文声称解决了关于 $\ell=2$ 及特定 $p$ 同余类下超奇异同构图脊柱结构的文献空白。通过提供显式直径函数以及一种通过平均直径检测边附着的手段，这项工作提供了一个预测脊柱连通性的工具。这对于理解基于同构的密码系统的安全参数具有重要意义，因为路径查找问题的难度与图的直径和连通性密切相关。

作者谦虚地指出，虽然数据揭示了强烈的趋势（例如 2 的上方素数生成类群的高频率），但样本量在“密码学意义上是微小的”，且结果是经验启发式而非适用于所有 $p$ 的证明定理。文章总结道，该方法可以推广到 [HAS26] 中的其他情况，并且观察到的短非附着边的缺乏值得进一步研究。