The Spine: A Supersingular Highway

技術要約：スパイン（背骨）：超特異な高速道路

問題提起
本論文は、有限体 $\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 119, 71 \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})$ の類群における $\ell$ の上の素数の位数である。
4. エッジの影響分析: 著者は、$\Theta$ によって追加される新しいエッジ $E$ の影響を、以下の三つのシナリオの下で分析している：
   • $E$ が積み重なったコンポーネントの内部にある場合。
   • $E$ が折り畳まれたコンポーネントの内部にある場合。
   • $E$ が二つの異なるコンポーネントを接続する場合（エッジ付着）。
5. 平均直径のヘリスティック: 本論文の主要な手法論的貢献は、「非連結グラフの平均直径」の定義である。論文では、エッジ付着が発生する場合にのみ、スパインの平均直径が厳密に増加することを証明している。これにより、計算された平均直径の値に基づいて構造的なケースを区別することが可能になる。
6. 計算による検証: カルガリー大学の MSX1 サーバーを使用し、指定された合同条件を満たす 10,000 個の素数（17,471 から 2,186,519 の範囲）について平均直径を計算した。これらの値は、クラス数 $h(-p)$ と $\text{ord}(\ell)$ から導かれた理論的境界と比較され、各素数におけるスパインの構造を分類するために用いられた。

主な貢献

• 明示的な直径公式: $\ell=2, p \equiv 71, 119 \pmod{120}$ の特定のケースにおける、折り畳まれたコンポーネントおよび積み重なったコンポーネントの距離、離心率、および直径関数の完全な導出を初めて提供した。
• 平均直径による構造的分離: 平均直径を計算することによって、エッジ付着と非付着のシナリオを区別する厳密な手法を確立した。$\text{ord}(\ell), h(-p)$, および平均直径からスパインの構造を決定するためのアルゴリズム（Algorithm 1）も提供されている。
• 経験的ヘリスティック: 広範な計算を通じて、エッジ付着の頻度と新しいエッジの所在の分布に関するデータ駆動型のヘリスティックを提供した。

結果
10,000 個の素数の計算研究により、以下の経験的な結果が得られた：

• 類群の生成: 約 77.93% のケースにおいて、2 の上の素数が類群を生成している（$h(-p) = \text{ord}(\ell)$）。これらの場合、スパインは折り畳まれたコンポーネントのみで構成され、エッジ付着は発生しない。
• エッジ付着の頻度: 積み重なったコンポーネントが存在する残りの 22.07% のケースにおいて、エッジ付着は約 67.29% の割合で発生している。
• エッジの所在: エッジ付着が発生する場合、折り畳まれたコンポーネントに関わる付着と、二つの積み重なったコンポーネント間の付着の間で、ほぼ均等な分割が見られる。
• 非付着エッジ: 付着が発生しない場合、新しいエッジがグラフの直径を減少させることは稀である（複数のコンポーネントを持つケースの約 3.08%）。
• 分布の異常: データは、新しいエッジが、純粋なランダム分布が示唆するよりも、折り畳まれたコンポーネント内の短い非付着エッジである可能性が低いことを示唆している。

意義
本論文は、$\ell=2$ かつ特定の合同類における $p$ に関する、超特異イソジェニーグラフのスパインの構造に関する文献の特定の空白を埋めるものである。明示的な直径関数と、平均直径によるエッジ付着の検出方法を提供することで、本研究はスパインの連結性を予測するためのツールを提供している。これは、経路探索問題の困難さがグラフの直径および連結性に結びついていることから、イソジェニーに基づく暗号システムのセキュリティパラメータを理解する上で重要である。

著者は、データが強い傾向（例えば、2 の上の素数が類群を生成するという高い頻度など）を示しているものの、サンプルサイズは「暗号学的には小さい」ものであり、結果はあくまで経験的なヘリスティックであると謙虚に述べている。論文は、この手法が [HAS26] の他のケースにも拡張可能であること、および観察された「短い非付着エッジ」の欠如はさらなる調査に値することを結論づけている。