🔢 mathematics

Deterministic and Efficient Ideal Arithmetic via Two-Element Representations

本文提出了一种确定性多项式时间算法，用于寻找数域中理想的两个元素的表示，特别处理了理想的范数与定义多项式阶的指数互质的情况，这涵盖了与格密码学相关的单代数域中所有的理想。

原作者： Qi Cheng

发布于 2026-06-26

📖 1 分钟阅读🧠 深度阅读

原作者： Qi Cheng

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

以下是该论文的通俗化解释，使用了日常类比。

大局观：简化混乱的房间

想象你正在一个非常复杂且高安全性的房间（代数数域）里工作。在这个房间里，有一些特定的区域被称为理想（Ideals）。这些区域包含了数字和多项式的集合。

在密码学（特别是“后量子”安全领域）的世界中，这些区域就像是保护数据的锁和钥匙。为了高效地使用这些锁，数学家需要用尽可能少的“钥匙”来描述每一个区域。

问题所在：
通常情况下，描述这样一个区域需要很长的生成元列表（比如需要 5 个或 10 个不同的钥匙才能打开一扇门）。论文指出，在数学上，你其实只需要两把钥匙就能打开这个房间里的任何一扇门。然而，找到这两把特定的钥匙一直是个噩梦。

旧的方法是随机的（就像不断猜测钥匙直到猜对为止），这既慢又不靠谱。
其他方法则对于现代加密中使用的巨大数字来说太慢了。

解决方案：
作者 Qi Cheng 发明了一个确定性的、快速的配方，无需猜测，每次都能找到那两把完美的钥匙。

三步配方

论文将解决方案分为三个阶段，我们可以将其比作整理一个凌乱的衣柜。

第一阶段：整理衣服（分解/因式分解）

想象你有一堆乱七八糟的衣服（你的输入理想）和一个巨大的数字 $N$ （就像是箱子上的标签）。

目标： 你想把这一大堆乱七八糟的衣服变成若干个整齐的小堆。
工具： 作者使用了**欧几里得算法（Euclidean Algorithm）**的一个改进版本（这是一种寻找公约数的经典数学方法）。你可以把它想象成一台按颜色对衣服进行分类的机器。
障碍： 有时机器会卡住，因为“织物”（数字 $N$ ）存在隐藏的缺陷（零因子）。
解决方法： 如果机器发现了缺陷，它不会崩溃；而是会将大箱子拆分成若干个没有这些缺陷的小箱子。它会不断重复这个过程，直到每个箱子都干净且易于处理。
结果： 你现在拥有了一系列更小、更简单的区域。有些已经很简单了（两把钥匙），有些虽然还有点乱，但处于一种可预测的格式中。

第二阶段：神奇的折叠（处理复杂的区域）

第一阶段中的某些箱子仍然很棘手。它们看起来需要很多把钥匙，但实际上它们只是一个“完全幂”（就像一个箱子里叠放着许多完全相同的更小的箱子）。

创新点： 作者引入了“广义 Dedekind 判别准则”。你可以把它想象成一种特殊的折叠技巧。
类比： 想象你有一根长而缠绕的绳子。你不能直接剪断它，你需要以特定的方式折叠它，使其变成一个整齐、紧凑的捆包。论文证明了对于这些特定的棘手箱子，存在一种数学上的“折叠”方式，可以将复杂的描述转化为简单的两把钥匙描述。
神奇技巧： 论文展示了如何找到一个“伙伴”钥匙。如果你已经有了一把钥匙，你可以通过数学计算出它的伙伴，这样它们两者结合在一起，就能完美地描述该区域，而不需要额外的钥匙。

第三阶段：拉链合拢（重新组装）

现在你拥有了一叠整齐的小箱子，每个箱子都有自己的两把钥匙。你需要把它们重新组合起来，以代表最初的那个大区域。

工具： 中国剩余定理（Chinese Remainder Theorem）。
类比： 想象你有几个装有拼图碎片的小密封袋。你想把它们全部装进一个大袋子里。这个定理就像是一个拉链，能完美地对齐所有小袋子的边缘，使它们合并成一个无缝的大袋子，且不会丢失任何碎片。
结果： 你得到了原始的区域，但现在它仅由两个元素（两把钥匙）来描述。

为什么这很重要（根据论文内容）

无需猜测： 与以往依赖运气的方法不同，这种方法是确定性的。如果你运行两次，你会得到完全相同的答案。
速度快： 它足以应对现代密码学中使用的巨大数字。它避免了需要将数字分解为质因数的过程（这就像试图通过“反向烘焙”蛋糕来取回鸡蛋和面粉一样——极其困难且缓慢）。
特定目标： 该方法完美适用于单子域（Monogenic Fields）。
- 类比： 把“单子域”想象成用标准模块化套件建造的房间。密码学中最重要的房间（使用如“Kyber”加密标准中的分圆多项式）正是以此种方式建造的。
- 论文声称，该算法适用于这些标准房间中的所有理想。
“证书”： 如果算法失败，它不会直接放弃；它会提供一个“证书”，证明该房间不是用标准的模块化套件建造的（即该域不是单子域）。

总结

本文提出了一种新的、可靠且快速的方法，用于简化加密中使用的复杂数学结构。与其使用一长串数字来描述一个数学“区域”，作者提供了一个循序渐进、非随机的配方，将该列表简化为仅有的两个数字。这使得用于安全通信的“算术”（数学运算）变得更快、更具可预测性。

技术摘要：通过二元素表示实现确定性且高效的理想算术

问题陈述
在计算数论和后量子密码学（特别是环学习误差问题，即 RLWE）中，高效的理想算术至关重要。虽然在理论上已知任何数域 $K$ 中的分式理想都可以由其整数环 $\mathcal{O}_K$ 上的两个元素生成，但寻找这种表示在计算上具有挑战性。现有的算法要么是随机性的，要么对于加密规模的输入而言是不切实际的，因为它们依赖于对理想范数或定义多项式判别式的昂贵素因子分解。此外，判断一个理想是否为主理想（由单个元素生成）仍然是一个开放问题，目前尚无已知的有效算法。

本文解决的具体问题是：给定一个在 $\mathcal{O}_K$ 中由一组生成元定义的理想（通常源自 $\mathbb{Z}$ -基或元组 $(N, a(\alpha), b(\alpha))$ ，其中 $N$ 是一个大的合数），寻找两个元素 $M, c(\alpha)$ ，使得该理想由 $M\mathcal{O}_K + c(\alpha)\mathcal{O}_K$ 生成。作者关注的是 $N$ 为不含小素因子的巨大合数的困难情况，在这种情况下，分解 $N$ 是不可行的。

方法论
本文提出了一种确定性的多项式时间算法，避免了素理想分解和随机性。该方法分为三个阶段，高度依赖于在 $\mathbb{Z}/N\mathbb{Z}$ 上的多项式算术以及德德金判别法（Dedekind criterion）的广义版本。

阶段 1：理想分解与归一化
算法尝试使用基于 $\mathbb{Z}/N\mathbb{Z}$ 上多项式的欧几里得风格算法来简化输入理想 $(N, a(\alpha), b(\alpha))$ 。
- 如果首项系数在 $\mathbb{Z}/N\mathbb{Z}$ 中是单位，算法会计算多项式的最大公约数（GCD），将理想简化为二元素形式 $(N, c(\alpha))$ 。
- 如果遇到非平凡零因子（表明 $N$ 是合数），算法将 $N$ 分解为互素的分量，并递归地处理生成的理想。
- 对于 $N$ 是完全幂次（ $N = N_0^e$ ）的情况，算法通过运行欧几里得算法来处理退化情况，从而产生形如 $(N^e, a_1(x), N d_1(x), \dots)$ 的理想。随后利用定义多项式 $f(x)$ 来确保 $a_1(x)$ 是 $f(x) \pmod N$ 的一个因子。
- 该阶段的输出是处于“特殊形式”下的理想乘积：要么是简单的二元素理想 $(N_i, a_i(\alpha))$ ，要么是涉及 $N$ 的幂次和多个生成元的特定结构的理想。
阶段 2：处理特殊形式与乘法
此阶段处理形式为 $(N^e, a(\alpha), N I)$ 且 $N$ 不是完全幂次的理想。
- 广义德德金判别法： 这是关键的技术贡献。作者引入了一个广义的德德金判别法（引理 5 和定理 3）。这使得算法能够找到一个首一多项式 $\tilde{a}(x)$ ，使得 $f(x) = \tilde{f}_1(x)N + \tilde{a}(x)A(x)$ ，并满足特定的互素条件 $(\tilde{a}(x), \tilde{f}_1(x), N) = 1$ 。
- 理想除法与乘法： 利用这种形式，算法构造出一个元素 $\bar{a}(\alpha)$ ，使得 $\tilde{a}(\alpha)\bar{a}(\alpha) \equiv N \pmod{N^s}$ 。这一性质使得在二元素表示下进行高效的理想除法和理想乘法成为可能。具体而言，它证明了只要生成元满足广义德德金条件，则 $(N, \tilde{a}_1(\alpha))(N, \tilde{a}_2(\alpha)) = (N^2, \tilde{a}_1(\alpha)\tilde{a}_2(\alpha))$ 。
- 算法迭代地将复杂的理想简化为简单二元素理想 $(N_i, \tilde{a}_i(\alpha))$ 的乘积。
阶段 3：通过中国剩余定理进行重组
一旦输入理想被分解为一对对互素的二元素理想 $(N_i, a_i(\alpha))$ 的乘积，算法便使用中国剩余定理（引理 2）将它们重新乘回成一个单一的二元素表示 $(M, c(\alpha))$ 。

核心贡献

确定性多项式时间算法： 本文提出了第一个在单项式域（monogenic fields）中寻找二元素表示的确定性算法（对于非单项式域，要求理想范数与指数 $[\mathcal{O}_K : \mathbb{Z}[x]/(f)]$ 互素），且无需进行范数的素因子分解。
广义德德金判别法： 作者引入了一个适用于合数模数 $N$ 的广义德德金判别法。这使得算法能够识别合适的生成多项式，从而在不知道 $N$ 的素因子的情况下，促进高效的理想乘法和除法。
处理合数模数： 不同于依赖素因子分解的现有方法（如 Pohst-Zassenhaus），该方法直接处理合数 $N$ 。它证明了寻找 $N$ 的因子是不必要的，事实上，如果目标仅仅是寻找表示，寻找因子反而会减慢处理速度。
高效性： 算法通过将昂贵的整矩阵（格）运算替换为多项式算术，显著降低了大规模输入的空间和时间复杂度。

结果与复杂度
主要结果（定理 1）指出，对于度数为 $n$ 的单项式域，二元素表示问题可以在 $\text{poly}(n, \log N)$ 时间内解决。

当 $N$ 是无平方因子（square-free）时，复杂度为 $O(n^2 \log N \cdot \omega(N))$ ，其中 $\omega(N)$ 是不同素因子的数量。由于 $\omega(N)$ 平均为 $\log \log N$ ，因此该复杂度与随机算法相当，但是确定性的。
该算法对于单项式多项式是实用的，这些多项式包括在格密码学（如 NewHope, Crystals-Kyber）中广泛使用的分圆多项式。
如果算法未能生成表示，它会提供一个证书，证明该域不是单项式的（或者指数条件未满足）。

意义与声明
本文声称通过消除对素因子分解和随机性的依赖，解决了理想算术中长期存在的低效问题。

密码学相关性： 这项工作直接支持基于理想格的后量子密码方案的实现，特别是那些使用分圆域的方案。
理论进展： 它将 Pohst-Zassenhaus 算法（受限于素范数）推广到了任意合数。
谦逊态度： 作者指出，虽然该算法适用于所有单项式域中的理想，但要将其扩展到非单项式域，需要理想范数与指数互素。他们还指出一个开放问题：如何在多项式时间内为给定的数域找到单项式多项式表示，这目前受到非本质判别子（inessential discriminant divisors）的阻碍。本文并不声称解决了通用的主理想问题或分解大整数的问题，而是旨在针对特定的理想表示任务绕过这些难题。