🔢 mathematics

Explicit Factorization of $X^n-1$ over $\mathbb{Z}_{p^e}$ via Cofactor-Free Single-Seed Hensel Lifting

本文通过引入模理想导数原理（Ideal Derivation Modulo Principle）和一种消除了经典方法计算瓶颈的无余因子亨塞尔提升（cofactor-free Hensel lifting）技术，提出了一种在 $\mathbb{Z}_{p^e}$ 上显式分解 $X^n-1$ 的高效框架，实现了近乎常数级的每层复杂度，并较现有实现方案实现了显著加速。

原作者： Yongchao Wang, Yang Ding, Jiansheng Yang, Zhiqiu Huang

发布于 2026-06-23

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： Yongchao Wang, Yang Ding, Jiansheng Yang, Zhiqiu Huang

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

想象一下，你面对着一把由特定金属（环 $\mathbb{Z}_{p^e}$ ）制成的巨大且复杂的锁。你的目标是找到所有能打开这把锁的独特钥匙。在数学世界中，这个“锁”是一个多项式方程 ( $X^n - 1$ )，而寻找这些“钥匙”的过程被称为分解（factorization）。

长期以来，如果锁是由简单的、平坦的金属（有限域）制成的，数学家们可以轻松找到这些钥匙。但当锁变得更厚、更复杂（由素数幂 $p^e$ 制成）时，旧有的工具就会失效。它们要么因为背负了过多的额外重量而变得极其沉重，要么会陷入一个无解的谜题中无法自拔。

本文介绍了一种全新的、巧妙的工具包，用于高效地破解这些复杂的锁。以下是他们是如何实现的，通过简单的类比进行解释：

1. 问题所在：“沉重的背包”与“死胡同”

作者解释说，以往的方法存在两个主要缺陷：

沉重的背包（全局余因子/Global Cofactors）： 旧方法需要背负一个巨大的“背包”，里面装满了额外的辅助信息（称为全局余因子），这个背包的大小会随着问题的规模同步增长。每当你试图让锁的精度提高一点点时，你就必须更新这个沉重的背包，这既缓慢又令人精疲力竭。
死胡同（雅可比矩阵求逆/Jacobian Inversion）： 另一种方法试图通过对一个巨大的数字矩阵进行求逆来直接求解钥匙。然而，在这种特定类型的金属中，某些数字表现得像是“零因子”（它们就像损坏的齿轮，会让机器卡死）。在这种情况下尝试对矩阵求逆会导致死胡同，迫使计算机进行盲目的猜测，这需要耗费无法想象的时间。

2. 解决方案：一个“种子”与一个“神奇配方”

作者创建了一个既能避免沉重背包，又能避开死胡同的框架。他们使用了三个技巧：

A. “单一种子”（母钥）

他们不是从头开始寻找每一把钥匙，而是先找到一把完美的钥匙（“种子”因子）。

类比： 想象你有一个母模印章。一旦你有了其中一把钥匙的设计，你就不需要再亲手雕刻每一把钥匙了。你只需要用机器去复制并调整这个设计，从而制作出所有的其他钥匙。
原理： 他们将这个单一种子从简单的薄层提升到复杂、厚实的锁层，而无需携带那个沉重的“背包”。他们通过在开始时仅缓存一次“神奇逆”（预先计算好的辅助工具）来实现这一点。

B. “神奇配方”（狄克逊递推/Dickson Recurrence）

一旦有了种子，他们就需要生成所有其他的钥匙。

类比： 想象一个蛋糕的配方。如果你知道了做一个蛋糕所需的原料，你就可以利用一套特定的规则（递推关系），通过改变几个数字，就能算出成千上万个同样大小的不同蛋糕的原料。
原理： 他们使用了一种被称为狄克逊递推的数学“配方”。这个配方利用这个单一种子来生成一长串“迹值”（trace values，类似于蓝图）。从这个蓝图中，他们可以立即重建出锁的每一个其他因子的系数。

C. “双轨制”组装线

最后，他们需要将这些蓝图数字还原为真正的钥匙。

类比： 想象一条工厂组装线。通常，我们会使用一台快速的标准机器（牛顿-吉拉德求逆法/Newton–Girard inversion）来组装零件。但如果零件有点“粘稠”（由于前面提到的零因子问题），标准机器就会卡住。
解决方案： 他们制造了一台备份机器（高斯消元法/Gaussian elimination），即使在零件“粘稠”时也能正常工作。系统会自动检查条件，并仅在必要时切换到备份机器。这确保了无论金属多么棘手，工厂的生产都不会停止。

3. 结果：速度与简洁

该论文声称这一新框架非常高效。

速度提升： 他们将这种方法与标准计算机软件（如 SageMath）进行了对比测试。其方法比标准引擎快了 445 倍，比他们之前的版本快了 33.5 倍。
效率： 增加锁的厚度（增加精度深度 $e$ ）对速度的影响微乎其微。这就像爬梯子，前几级台阶可能比较吃力，但一旦你爬上去，之后的每一步都只需要极小的努力。

为什么这很重要？（根据论文所述）

作者指出，这对现代技术的三个特定领域至关重要：

后量子密码学（Post-Quantum Cryptography）： 旨在保护数据免受未来量子计算机威胁的新安全标准，依赖于这些数学结构。
全同态加密（Fully Homomorphic Encryption）： 一种可以在不解密的情况下对加密数据进行计算的技术。这种方法可以实现更高效的数据处理“插槽”。
代数编码理论（Algebraic Coding Theory）： 为现代通信系统（如 5G 或卫星链路）设计更好的纠错码。

简而言之，这篇论文提供了一种“智能、轻量且防卡顿”的方法，用于拆解复杂的数学锁，使得支撑下一代安全与通信的底层数学运算变得更加快速且可靠。

技术摘要：通过无余因子单种子 Hensel 提升实现 $X^n - 1$ 在 $\mathbb{Z}_{p^e}$ 上的显式分解

1. 问题陈述

本文研究了在整数剩余环 $\mathbb{Z}_{p^e}$ 上（其中 $\gcd(n, p) = 1$ ）对多项式 $X^n - 1$ 进行显式分解的问题。这一操作对于后量子密码学（特别是像 ML-KEM 和 ML-DSA 这样的格密码方案）、涉及明文槽填充（plaintext slot packing）的全同态加密（FHE），以及代数编码理论（有限链环上的循环码）具有基础性意义。

虽然在有限域 $\mathbb{F}_p$ 上的分解已得到充分研究，但将这些分解提升到 $\mathbb{Z}_{p^e}$ 时，现有方法面临严重的算法瓶颈：

多项式 Hensel 提升（Polynomial Hensel Lifting）： 需要维护并更新阶数为 $O(n)$ 的全局余因子（global cofactors），导致每个精度层级的计算成本极高。
多元 Newton–Hensel 迭代（Multivariate Newton–Hensel Iteration）： 试图直接提升因子系数，但需要在每一层反转一个 $m \times m$ 的 Jacobian 矩阵（其中 $m$ 是陪集维度）。在 $\mathbb{Z}_{p^e}$ 上，零因子阻碍了标准的求逆过程，迫使算法进行复杂度为 $O(p^{(m-1)^2})$ 的穷举搜索。

目前的计算机代数系统（如 SageMath）在处理 $e > 5$ 的此类分解时，往往缺乏通用支持，经常抛出 NotImplementedError 错误。

2. 方法论

所提出的框架通过一种三阶段方法消除了上述瓶板，该方法将全局阶数 $n$ 与提升过程解耦，并避免了 Jacobian 矩阵的反转。

2.1. 多元 Dickson 递推与迹生成

该框架利用 多元 Dickson 递推（Multivariate Dickson Recurrence），通过单个“种子”多项式生成所有不可约因子的幂和迹（power sum traces）。

种子发现（Seed Discovery）： 在 $\mathbb{F}_p$ 上找到一个度数为 $m$ 的单项不可约因子 $G(X)$ 。
迹传播（Trace Propagation）： 利用 Newton–Girard 等式和由种子系数定义的线性反馈移位寄存器（LFSR）结构，生成全局迹数组 $\{S_k\}_{k=1}^n$ 。该数组编码了 $X^n - 1$ 分解中所有维度为 $m$ 的不可约因子的系数信息。
陪集分发（Coset Dispatch）： 使用 多重等差（Multiple Equal-Difference, MED） 分解来划分循环陪集。分发机制用于恢复特定陪集的内在迹，通过模缩放处理全秩情况（ $m_s = m$ ）和退化情况（ $m_s < m$ ）。

2.2. 模原理下的理想导出

本文建立了一个将分解坐标与多项式理想联系起来的理论基础。

定理 3（理想导出模原理）： 通过将 $X^n - 1$ 除以一个通用的单项多项式 $G(A, X)$ （其中系数 $A$ 为不定元），得到一个度数 $< m$ 的余式 $R(A, X)$ 。该余式的系数生成了一个理想 $I_{n,m}$ 。
意义： 该理想在 $\mathbb{F}_p$ 中的根恰好对应于 $X^n - 1$ 不可约因子的系数。这将其研究范围从特定的情形（如 $n=p+1$ ）推广到了任意的 $n$ 和 $m$ 。

2.3. 无余因子单种子 Hensel 提升

为了将种子因子从 $\mathbb{F}_p$ 提升到 $\mathbb{Z}_{p^e}$ ，该框架采用了 无余因子 Hensel 提升（Cofactor-Free Hensel Lift）（定理 4）。

机制： 该方法不再更新全局余因子或反转 Jacobian 矩阵，而是利用在 $\mathbb{F}_p$ 上预先计算并缓存的多项式逆，来提升单个种子因子。
效率： 这将每层提升的成本降低到 $O(m^2)$ 次代数运算，且与全局阶数 $n$ 无关，也与精度深度 $e$ 无关。

2.4. 双轨系数重构

一旦迹被分发，框架使用双轨策略重构剩余因子的系数：

主轨（ $p > m$ ）： 使用 Newton–Girard 等式进行显式求逆，因为对于所有 $k \le m$ ， $k$ 在 $\mathbb{Z}_{p^e}$ 中都是可逆的。
回退轨（ $p \le m$ ）： 当 $p$ 整除 $k$ 时，Newton–Girard 求逆失效。框架切换到商环高斯消元法，将根表示在 $\mathbb{Z}_{p^e}[X]/\langle G_{seed}(X) \rangle$ 中，并通过求解系数矩阵的左零空间来求解多项式。Frobenius 自同构保证了其可解性。

3. 主要贡献

理想导出模原理： 一个通用的定理，通过模余式提取出的多元 Dickson 多项式理想，将所有因子系数表征为该理想的根。
无余因子 Hensel 提升： 一种提升算法，通过使用缓存的逆，将单个种子因子提升至 $\mathbb{Z}_{p^e}$ ，从而消除了对全局余因子更新或 Jacobian 矩阵反转的需求。
双轨重构： 一种鲁棒的机制，用于从迹数组中恢复因子系数，结合了 Newton–Girard 求逆与商环高斯消元法，以处理所有特征象限（ $p > m$ 和 $p \le m$ ）。

4. 结果与复杂度

论文提供了理论复杂度界限和实证评估：

理论复杂度： 在 $\mathbb{Z}_{p^e}$ $Z_{p^{e}}$ 上显式分解 $X^n - 1$ $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$ 时，每层提升成本接近常数的特性。

5. 意义

本文声称填补了计算机代数系统中的一个关键空白，即目前缺乏针对任意 $n$ 且 $e > 5$ 的 $X^n - 1$ 在 $\mathbb{Z}_{p^e}$ 上的通用分解工具。通过消除与多元 Jacobian 矩阵反转相关的指数壁垒，以及与全局阶数 $n$ 相关的余因子更新线性依赖，该框架使得以下应用成为可能：

参数探索： 在任意精度深度下，高效探索 FHE 方案中的槽填充（slot-packing）参数。
高级密码结构： 支持使用复合模数 $q = p^e$ 或一般循环阶 $n$ 的格方案，扩展了目前 NIST 标准对素数模数及 2 的幂次方的限制。
编码理论： 高效构建有限链环上的循环码和幂等生成器，这对于使用相移键控（PSK）的现代通信系统至关重要。

这项工作不仅将 $X^n - 1$ 的分解视为一个理论练习，更将其定位为下一代密码学和编码应用的实际赋能者，克服了经典提升方法所面临的“严重性能墙”。