技術要約：単一シード・ヘンゼル・リフティングによる $\mathbb{Z}_{p^e}$ 上の $X^n - 1$ の明示的因数分解

1. 問題提起

本論文は、$\gcd(n, p) = 1$ であるときの整数剰余環 $\mathbb{Z}_{p^e}$ 上における多項式 $X^n - 1$ の明示的な因数分解を扱う。この操作は、ポスト量子暗号（特にML-KEMやML-DSAのような格子ベースのスキーム）、プレーンテキスト・スロット・パッキングを伴う完全準同型暗号（FHE）、および代数的符号理論（有限鎖環上の巡回符号）において極めて重要である。

有限体 $\mathbb{F}_p$ 上での因数分解は十分に理解されているが、これらの因数分解を $\mathbb{Z}_{p^e}$ へとリフト（持ち上げ）する際には、既存の手法において深刻なアルゴリズム上のボトルネックが生じる：

• 多項式ヘンゼル・リフティング（Polynomial Hensel Lifting）: 次数 $O(n)$ のグローバルな余因子（cofactor）を維持および更新する必要があり、各精度レイヤーにおける計算コストが高くなる。
• 多変数ニュートン・ヘンゼル反復（Multivariate Newton–Hensel Iteration）: 各レイヤーで係数を直接リフトしようとするが、その際 $m \times m$ のヤコビ行列（$m$ は余剰類の次元）の逆行列計算を必要とする。$\mathbb{Z}_{p^e}$ 上では零因子が標準的な逆行列計算を阻害するため、指数関数的な複雑度 $O(p^{(m-1)^2})$ を伴う全探索を強いることになる。

現在の計算代数システム（SageMathなど）は、多くの場合 $e > 5$ のときのこれらの因数分解に対する汎用的なサポートを欠いており、NotImplementedError を発生させることが多い。

2. 手法

提案されたフレームワークは、グローバルな次数 $n$ をリフティングのプロセスから分離し、ヤコビ行列の逆行列計算を回避することで、上述のボトルネックを排除する3段階のアプローチを採用している。

2.1. 多変数ディクソン漸化式とトレース生成

本フレームワークは、単一の「シード」多項式からすべての既約因数の冪和トレースを生成するために、**多変数ディクソン漸化式（Multivariate Dickson Recurrence）**を利用する。

• シードの発見: $\mathbb{F}_p$ 上の次数 $m$ の単項既約因子 $G(X)$ を一つ見出す。
• トレースの伝播: ニュートン・ギルド恒等式と、シードの係数によって定義される線形帰還シフトレジスタ（LFSR）構造を用いて、グローバルなトレース配列 $\{S_k\}_{k=1}^n$ を生成する。この配列は、$X^n - 1$ の因数分解に含まれるすべての既約因数の係数情報をエンコードしている。
• 余剰類へのディスパッチ: **多重等差（Multiple Equal-Difference: MED）**分解を用いて、巡回余剰類を分割する。ディスパッチ機構により特定の余剰類の固有トレースを回収し、フルランクのケース（$m_s = m$）と退化したケース（$m_s < m$）の両方を、モジュロ・スケーリングを介して処理する。

2.2. 剰余原理によるイデアル導出

本フレームワークは、因数分解の座標と多項式イデアルを結びつける理論的基礎を確立している。

• 定理3（イデアル導出剰余原理）: 未定係数 $A$ を持つ単項多項式 $G(A, X)$ による $X^n - 1$ の多項式長除算を行うことで、次数 $< m$ の剰余 $R(A, X)$ を得る。この剰余の係数がイデアル $I_{n,m}$ を生成する。
• 意義: このイデアルの $\mathbb{F}_p$ における根は、$X^n - 1$ の既約因数の係数と正確に一致する。これは、特定のケース（例：$n=p+1$）に関する先行研究を、任意の $n$ および $m$ へと一般化するものである。

2.3. 余因子フリー・シングルシード・ヘンゼル・リフティング

$\mathbb{F}_p$ から $\mathbb{Z}_{p^e}$ へシード因子をリフトするために、本フレームワークは余因子フリー・ヘンゼル・リフト（Cofactor-Free Hensel Lift）（定理4）を採用している。

• メカニズム: グローバルな余因子を更新したりヤコビ行列を反転させたりする代わりに、一度 $\mathbb{F}_p$ 上で計算されたキャッシュ済みの多項式逆元を用いて、単一のシード因子を昇格させる。
• 効率性: これにより、1レイヤーあたりのリフティング・コストを、グローバルな次数 $n$ や精度深さ $e$ に依存しない $O(m^2)$ 代数演算へと削減する。

2.4. デュアルトラック係数再構成

トレースがディスパッチされた後、フレームワークは以下のデュアルトラック戦略を用いて残りの因数の係数を再構成する。

1. プライマリー・トラック ($p > m$): すべての $k \le m$ に対して $k$ が $\mathbb{Z}_{p^e}$ 内で可逆であるため、明示的な逆転算のためにニュートン・ギルド恒等式を使用する。
2. フォールバック・トラック ($p \le m$): $p$ が $k$ を割り切る場合、ニュートン・ギルドによる逆転算が失敗する。このとき、フレームワークは商環上のガウス消去法へと切り替え、根を $\mathbb{Z}_{p^e}[X]/\langle G_{seed}(X) \rangle$ 内で表現し、係数行列の左零空間における多項式を解く。フロベニウス自己同型が解の存在を保証する。

3. 主な貢献

1. イデアル導出剰余原理: モジュロ剰余抽出を介して得られる多変数ディクソン多項式イデアルから、すべての因数係数を特性付ける一般的な定理を提示した。
2. 余因子フリー・ヘンゼル・リフト: キャッシュされた逆元を用いて単一のシード因子を $\mathbb{Z}_{p^e}$ へ昇格させるリフティング・アルゴリズムを提供し、グローバルな余因子更新やヤコビ行列の逆行列計算を排除した。
3. デュアルトラック再構成: ニュートン・ギルドによる逆転算と商環上のガウス消去法を組み合わせることで、すべての特性レジーム（$p > m$ および $p \le m$）に対応し、トレース配列から因数の係数を回収する堅牢なメカニズムを実現した。

4. 結果と複雑度

本論文は、理論的な計算量境界と経験的な評価の両方を提供している。

• 理論的複雑度: $\mathbb{Z}_{p^e}$ 上の $X^n - 1$ を明示的に因数分解するための総代数計算量は $O(n + m^3 \log p + e \cdot m^2)$ に抑えられる。
  • $O(n)$ 項はトレース生成を、
  • $O(m^3 \log p)$ 項はシードの発見を、
  • $O(e \cdot m^2)$ 項はリフティング過程（これは各レイヤーにおいてほぼ定数である）をそれぞれ表す。
• 実証的パフォーマンス:
  • 本フレームワークは、SageMathのC言語実装であるFLINT/Pariエンジン（実行時のオートシーディング・オーバーヘッドを含む）に対して 445倍の高速化 を達成した。
  • 著者らの以前の「V1」スカラー・リフト法に対して 33.5倍の高速化 を達成した。
  • 精度深さが $e = 1000$ を超える場合でも、リフティングの1レイヤーあたりのコストがほぼ一定であることを検証した。

5. 重要性

本論文は、任意の $n$ および $e > 5$ における $\mathbb{Z}_{p^e}$ 上の $X^n - 1$ の因数分解に対する汎用的なツールを欠いているという、現在の計算代数システムの決定的な欠落を埋めるものである。多変数ヤコビ行列の逆行列計算に伴う指数関数的な障壁、および余因子更新に伴うグローバル次数 $n$ への線形依存性を排除することで、本フレームワークは以下を可能にする：

• パラメータ探索: 任意の精度深さにおけるFHEスキームのスロット・パッキング・パラメータの効率的な探索。
• 高度な暗号構造: 素数冪（$q = p^e$）や一般的な巡回次数 $n$ を用いる格子ベース・スキームへの対応（現在のNIST標準が素数または2のべき乗に制限されている範囲を超えた拡張）。
• 符号理論: 現代の位相偏移変調（PSK）で使用される有限鎖環上の巡回符号および冪等生成子の効率的な構築。

本研究は、$X^n - 1$ の因数分解を単なる理論的な演習としてではなく、古典的なリフティング手法における「深刻なパフォーマンスの壁」を打破し、次世代の暗号および符号化アプリケーションを実用的に支えるための基盤として位置づけている。