🔢 mathematics

Explicit Factorization of $x^{p+1}-1$ over $\mathbb{Z}_{p^e}$ : A Structural Approach via Dickson Polynomials

本文通过建立多项式提升过程与狄克逊多项式根之间的结构同构，提出了名为 Dickson-Engine 的线性时间算法以显式分解 $\mathbb{Z}_{p^e}$ 上的 $x^{p+1}-1$ ，并据此构造出具有近最优参数的线性互补对偶码，为后量子密码学和量子纠错提供了无需纠缠消耗的高效资源。

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

发布于 2026-04-22

📖 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生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

这篇论文讲述了一个关于**“如何快速拆解数学积木”的故事，以及这个发现如何帮助我们要建造更坚固的“数字城堡”**（用于保护未来的量子计算机安全）。

为了让你轻松理解，我们可以把这篇论文的核心内容想象成一次**“从粗糙原石到精美珠宝”**的炼金术之旅。

1. 背景：我们要拆什么？（ $x^{p+1}-1$ ）

想象你有一块巨大的、坚硬的数学积木，它的名字叫 $x^{p+1}-1$ 。

普通情况：在简单的数学世界里（比如普通的数字 $p$ ），这块积木很容易拆成几块小积木（因式分解）。
困难情况：但在更复杂的数学世界里（叫 $Z_{p^e}$ ，你可以把它想象成积木表面覆盖了一层厚厚的、坚硬的“量子涂层”），这块积木变得非常难拆。

为什么要拆它？
因为拆开的每一块小积木，都可以用来制造**“数字盾牌”（编码理论中的 LCD 码）。这些盾牌对于未来的量子计算机**至关重要，能防止黑客攻击，保护我们的数据。

2. 旧方法：笨重的“敲石头”法（Hensel 引理）

以前，数学家们想拆开这块覆盖着涂层的积木，用的是**“Hensel 引理”**。

比喻：这就像是用一把钝锤子，一下一下地敲击积木。
- 先敲一下，看看裂开没；
- 再敲一下，调整角度；
- 再敲一下……
- 这个过程是迭代的（一步一步来），非常慢，而且你完全不知道下一锤会敲出什么形状，只能盲目地试。
缺点：如果积木很大（ $p$ 很大），这种方法慢得像蜗牛，而且掩盖了积木内部原本美丽的结构。

3. 新发现：迪克森多项式（Dickson Polynomials）—— 积木的“基因密码”

这篇论文的作者（王勇超等）发现了一个惊人的秘密：这块积木的拆解方式不是随机的，而是遵循一个隐藏的“基因密码”！

比喻：他们发现，积木内部藏着一张**“藏宝图”，这张图叫迪克森多项式（Dickson Polynomials）**。
- 这就好比，以前你是靠猜怎么拆积木，现在你手里有了3D 打印蓝图。
- 你不需要再拿锤子敲了，只要看一眼蓝图，就能直接知道每一块小积木长什么样，以及它们是怎么排列的。
- 这个蓝图的核心是一个叫 $V(x)$ 的“万能钥匙”。只要算出这个钥匙的数值，剩下的所有步骤就都是简单的算术题了。

4. 核心突破：Dickson-Engine（迪克森引擎）

基于这个发现，作者开发了一个叫 "Dickson-Engine" 的超级工具。

比喻：
- 旧方法：像是一个老工匠，用手工一点点打磨石头，做 100 个零件要一天。
- 新方法：像是一个全自动的 3D 打印机。它利用“基因密码”直接生成零件。
效果：
- 速度提升了 300 多倍！
- 以前需要几秒甚至几分钟才能算完的复杂数学题，现在眨眼间（0.02 秒）就搞定了。
- 它把复杂的“多项式运算”变成了简单的“整数加减乘除”，就像把解微积分题变成了做小学算术题。

5. 实际应用：建造“最坚固的盾牌”

作者用这个新工具，在数学世界里（ $Z_{169}$ ）建造了一组新的**“数字盾牌”**（LCD 码）。

惊人的发现：打破对称，反而更强！
- 通常我们认为“对称”是完美的。但在这些盾牌里，作者发现了一个反直觉的现象：“鲁棒性高原”（Robustness Plateau）。
- 比喻：想象你在搭乐高。如果你把左右完全对称的积木拼在一起（对称选择），搭出来的塔虽然整齐，但很脆弱，一推就倒（距离 $d$ 较小）。
- 但是，如果你故意打破对称，把左右不对称的积木拼在一起（打破共轭对），虽然看起来乱一点，但塔变得异常坚固，怎么推都推不倒（距离 $d$ 保持很高，甚至达到 120）。
- 这意味着，通过这种新方法，他们造出了接近理论极限的超级盾牌。

6. 总结：这对我们意味着什么？

速度极快：以前需要超级计算机算很久的数学题，现在普通电脑瞬间就能算完。
更安全：这些新造的“盾牌”能更好地保护数据，特别是针对未来的量子计算机（Post-Quantum Cryptography）。
零消耗：这些盾牌在保护量子信息时，不需要消耗额外的“纠缠资源”（就像不需要额外买电池就能跑得很远）。

一句话总结：
这篇论文就像发现了一种**“数学魔法”**，它把原本需要笨重敲击才能拆开的复杂数学积木，变成了一键生成的精美拼图。这不仅让计算速度快了 300 倍，还帮我们造出了未来量子时代最坚固的“防盗门”。

这是一份关于论文《 $x^{p+1}-1$ 在 $\mathbb{Z}_{p^e}$ 上的显式分解：基于 Dickson 多项式的结构方法》的详细技术总结。

1. 研究背景与问题 (Problem)

核心问题：如何在整数剩余环 $\mathbb{Z}_{p^e}$ （其中 $p$ 为奇素数， $e \ge 1$ ）上对多项式 $x^{p+1}-1$ 进行显式分解。
重要性：
- 该分解是构建具有厄米特对称性（Hermitian symmetry）的循环码的关键，这类码是构造线性互补对偶（LCD）码和纠缠辅助量子纠错码（EAQECC）的基础资源。
- 对于后量子密码学（基于格密码的 LCD 码）和量子纠错（无需纠缠消耗， $c=0$ ）至关重要。
现有挑战：
- 传统方法依赖Hensel 引理进行提升（Lifting），即从 $\mathbb{F}_p$ 逐步提升到 $\mathbb{Z}_{p^e}$ 。
- 这种方法本质上是迭代的，将系数视为黑盒逐步修正，计算复杂度高（通常为 $O(p^2)$ 或更高），且掩盖了底层的代数结构。
- 现有的结构化尝试（如基于牛顿和的提升）仍受限于迭代过程，且转换回系数时计算开销大。

2. 方法论 (Methodology)

论文提出了一种基于Dickson 多项式的结构性同构方法，将复杂的提升过程转化为标量根的查找问题。

2.1 理论基础：Dickson 多项式与系数生成

底层生成：在基域 $\mathbb{F}_p$ $F_{p}$ 上， $x^{p+1}-1$ $x^{p + 1} - 1$ 的不可约因子系数 $A_i$ $A_{i}$ 并非随机，而是由 Dickson 多项式 $D_n(x, \gamma)$ $D_{n} (x, γ)$ 递归生成。
- 若 $f(x) = x^2 - a_1x + a_2$ 是 $\mathbb{F}_p$ 上的本原多项式，则首项系数 $A_1 = D_{p-1}(a_1, a_2)$ 。
- 后续系数通过递推 $A_i = D_i(A_1, 1)$ 生成。
结构变量转换：引入结构变量 $S_i = 2 - A_i^2$ 。利用对称性（ $A_j = -A_i$ ），将因子对 $(x^2 - A_i x + 1)(x^2 + A_i x + 1)$ 转化为 $x^4 + S_i x^2 + 1$ 的形式。

2.2 核心创新：辅助多项式 $V(x)$ 与结构同构

发现：作者发现提升过程中的约束条件满足一个特定的辅助多项式方程 $V(S) \equiv 0 \pmod{p^h}$ 。
$V(x)$ 的定义： $V(x)$ $V (x)$ 的系数由二项式系数（帕斯卡三角形）的特定对角线切片决定，完全由素数 $p$ $p$ 决定，与具体的因子无关。
- 例如，当 $p=13$ 时， $V(x) = x^3 - x^2 - 2x + 1$ 。
结构同构定理：多项式 $x^{p+1}-1$ $x^{p + 1} - 1$ 在 $\mathbb{Z}_{p^e}$ $Z_{p^{e}}$ 上的分解提升，等价于在 $\mathbb{Z}_{p^e}$ $Z_{p^{e}}$ 上求 $V(x)$ $V (x)$ 的根。
- 这打破了传统的“逐个系数迭代提升”模式，将问题转化为标量根的线性提升。

2.3 算法实现：Dickson-Engine

基于上述理论，提出了确定性算法 Dickson-Engine：

初始化：在 $\mathbb{F}_p$ 上利用 Dickson 映射生成种子 $A_1$ 和 $S_1$ 。
预计算：构建 $V(x)$ 并计算更新因子。
线性提升循环：利用 $S^{(h+1)} = S^{(h)} + u \cdot V(S^{(h)})/p^h$ 进行提升，避免多项式模运算。
恢复系数：通过牛顿法从 $S$ 恢复 $A$ 。

复杂度：时间复杂度为 $O(e \cdot p)$ ，即线性时间，远优于传统库（如 NTL）的 $O(p^2)$ 。

3. 主要贡献 (Key Contributions)

理论突破：建立了 Dickson 多项式递归结构与 $\mathbb{Z}_{p^e}$ 上多项式提升过程之间的结构性同构。揭示了 $x^{p+1}-1$ 的分解由固定的辅助多项式 $V(x)$ 的根显式编码。
算法创新：开发了 Dickson-Engine（开源 C 实现）。
- 实现了线性时间复杂度 $O(ep)$。
- 相比标准库（NTL）实现了 300 倍以上 的加速。
- 完全避免了复杂的多项式算术和矩阵运算。
新码族构造：利用该引擎在 $\mathbb{Z}_{13^2}$ 上构造了长度 $n=182$ 的 LCD 码族，并发现了独特的“鲁棒性平台”现象。

4. 实验结果 (Results)

4.1 性能评估

基准测试：在 Intel Core Ultra 9 工作站上，针对 $p$ $p$ 从 100 到 10,000 的素数进行测试。
- NTL (Cantor-Zassenhaus)：执行时间随 $p$ 呈超线性增长（ $O(p^2 \log p)$ ）， $p \approx 10,000$ 时超过 5 秒。
- Dickson-Engine：执行时间几乎恒定（ $<0.02$ 秒），验证了 $O(p)$ 的线性复杂度。
提升效率：随着精度 $e$ 从 1 增加到 100，运行时间呈严格线性增长。

4.2 码构造与参数

场景： $p=13, e=2$ ，分解 $x^{14}-1$ ，通过 Gray 映射得到 $\mathbb{F}_{13}$ 上长度 $N=182$ 的线性码。
近最优参数：
- 构造了参数为 $[182, 1, 168]_{13}$ 和 $[182, 2, 144]_{13}$ 的 LCD 码，接近理论 Griesmer 界。
“鲁棒性平台” (Robustness Plateau)：
- 发现当维数 $k$ 从 4 增加到 12 时，最小距离 $d$ 保持稳定在 120 左右。
- 关键发现：在 $k=4$ 时，打破共轭对（即不选择互为相反数的系数对）的生成多项式，其最小距离（ $d=120$ ）显著优于保持共轭对完整（ $d \le 84$ ）的情况。
- 机理：保持共轭对会导致生成多项式稀疏（奇次项抵消），产生低重码字；打破共轭对则产生稠密多项式，增强了纠错能力。

5. 意义与影响 (Significance)

后量子密码学：提供了高效构造 LCD 码的工具，这类码对于抵抗基于格的密码系统中的 Hull 攻击至关重要。
量子纠错：构造的码具有零纠缠消耗（ $c=0$ ）的特性，可直接用于构建纯量子纠错码，且保留了循环结构，利于硬件实现。
代数编码理论：将多项式分解从“黑盒迭代计算”转变为“显式代数结构生成”，为研究局部环上的其他循环码（如分圆多项式 $\Phi_n(x)$ ）提供了新的理论框架。
设计原则：揭示了在局部环上构造高距离码时，打破代数对称性（Breaking Symmetry）可能比保持对称性更能获得优异的纠错性能，这是一个反直觉但极具价值的设计洞察。

总结：该论文通过引入 Dickson 多项式和辅助多项式 $V(x)$ ，彻底改变了 $x^{p+1}-1$ 在 $\mathbb{Z}_{p^e}$ 上的分解范式，不仅实现了计算效率的质的飞跃，还通过结构化的分析发现了新型高性能 LCD 码的构造规律。

1. 背景：我们要拆什么？（xp+1−1x^{p+1}-1xp+1−1）