环与域计算器

环与域计算器

环与域计算器可在两种最重要的有限代数结构族中进行精确算术运算：模环 Z_n 和伽罗瓦有限域 GF(p^k)。它支持加、减、乘、除、幂、乘法逆元和元素阶，并为每个结果丰富了结构分析 —— 单位、零因子、幂零元、幂等元、本原根和全颜色编码的 Cayley 表。

Z_n — 模环

对于正整数 n，环 Z_n = {0, 1, 2, …, n − 1} 承载了模 n 的加法和乘法。一个元素 a 是 Z_n 的单位（即具有乘法逆元）当且仅当 gcd(a, n) = 1，因此乘法群 Z_n* 的阶为 φ(n)，即欧拉函数值。

当 n 为合数时，满足 gcd(a, n) > 1 的元素 a 是零因子：存在 b ≠ 0 使得 a · b ≡ 0 (mod n)。计算器会自动将每个元素分类到其结构角色中。

寻找逆元 — 扩展欧几里得算法

如果 gcd(a, n) = 1，扩展欧几里得算法会产生整数 x, y，满足 a · x + n · y = 1，从而 a⁻¹ ≡ x (mod n)。只要您请求逆元，本工具就会显示生成的贝祖等式（Bézout identity）。

乘法阶

对于单位 a，乘法阶 ord(a) 是使得 a^k ≡ 1 (mod n) 的最小正整数 k ≥ 1。根据拉格朗日定理，ord(a) 整除 φ(n)。满足 ord(a) = φ(n) 的元素称为本原根，它生成整个单位群。本原根仅在 n 为 1, 2, 4, p^k, 或 2p^k（其中 p 为奇素数）时存在。

GF(p^k) — 有限（伽罗瓦）域

对于每个素数 p 和正整数 k，存在唯一的（在同构意义下）具有 p^k 个元素的域：伽罗瓦域 GF(p^k) = 𝔽_p^k。其元素表示为 GF(p) = Z_p 上次数 < k 的多项式，算术运算模次数为 k 的不可约多项式 f(x) 进行。

计算器为常见的 (p, k) 组合建议标准不可约多项式，例如 GF(4) 为 x² + x + 1，GF(8) 为 x³ + x + 1，GF(16) 为 x⁴ + x + 1，GF(9) 为 x² + 1。您可以自定义修改；本工具通过 Rabin 风格的 gcd 测试验证不可约性。

为什么 f(x) 必须不可约？

如果 f(x) 可分解为 g(x)·h(x) 且 deg g, deg h ≥ 1，那么 g(x) 和 h(x) 在商环中的映射将是非零零因子 —— 商环将只是一个环，而不是一个域。不可约性正是 GF(p)[x] / ⟨f(x)⟩ 成为域的必要条件。

多项式算术与逆元

加法是模 p 的系数对加。乘法是普通多项式乘法后取模：给定 a(x)·b(x)，除以 f(x) 并保留余数 r(x)，且 deg r < k。乘法逆元源于多项式环 GF(p)[x] 上的扩展欧几里得算法：寻找 u(x) 和 v(x) 使得 u(x)·a(x) + v(x)·f(x) = 1。

环与域对比一览

如何使用计算器

1. 选择结构 — 模整数选择 Z_n，扩展域选择 GF(p^k)。表单会重新排列以仅显示相关字段。
2. 输入参数 — 模数 n，或素数 p 和次数 k。对于 GF(p^k)，您可以将不可约多项式留空，计算器将填入标准多项式。
3. 选择操作 — 七个选项涵盖了所有常见任务：加、减、乘、除、求幂、计算逆元或查找乘法阶。
4. 提供操作数 — Z_n 输入整数，GF(p^k) 输入多项式如 x^2 + x + 1。系数列表形式（如 1,1,1）同样适用。
5. 点击计算。您将看到结果以及逐步计算过程、每个元素的分类，以及当结构足够小时显示的 Cayley 表。

计算示例 — GF(8) = GF(2³)

取 f(x) = x³ + x + 1（在 GF(2) 上不可约）。将 a(x) = x + 1 乘以 b(x) = x²：

乘法群 GF(8)* 是 7 阶循环群，元素 x 是本原元，因为当 k = 1, 2, …, 7 时，x^k 遍历了每个非零元素。

为什么这很重要

• 密码学 — AES 使用 GF(2⁸) 算术，其中 f(x) = x⁸ + x⁴ + x³ + x + 1。椭圆曲线密码学和离散对数问题存在于 GF(p) 和 GF(p^k) 中。
• 纠错码 — Reed-Solomon 和 BCH 码（用于 CD、二维码、DVB-T、旅行者号太空探测器）构建于 GF(2⁸) 或 GF(2^m) 上的多项式。
• 组合设计 — 有限域用于构建阿达玛矩阵、投影平面和用于统计实验的拉丁方。
• 计算机代数 — 分解和模约化算法（Berlekamp, Cantor-Zassenhaus）是在有限域上制定的。
• 数论教学 — Z_n、本原根和二次剩余是通往模算术、RSA 和 Diffie-Hellman 的大门。

常见问题

Z_n 何时是一个域？

模环 Z_n 是一个域当且仅当 n 是素数。在这种情况下，每个非零元素都是单位，因为对于每个 0 < a < n，gcd(a, n) = 1。当 n 是合数时，Z_n 具有零因子，仅是一个环，而不是一个整环。

什么是 GF(p^k)？

GF(p^k)，也称为阶为 p^k 的伽罗瓦域，是具有 p^k 个元素的唯一有限域。其元素表示为 GF(p) 上次数小于 k 的多项式，算术运算以次数为 k 的不可约多项式 f(x) 为模进行。对于每个素数 p 和正整数 k，在同构意义下恰好存在一个这样的域。

什么是不可约多项式，为什么需要它？

GF(p) 上的不可约多项式是不能分解为具有 GF(p) 中系数的低次数多项式的多项式。以次数为 k 的不可约多项式取模会得到一个作为域的商环。如果没有不可约性，商环将具有零因子，而不是一个域。

什么是零因子？

环中一个非零元素 a 如果存在一个非零元素 b 使得 a · b = 0，则 a 被称为零因子。在 Z_n 中，零因子恰好是 gcd(a, n) 大于 1 的元素 a。域没有零因子，这就是为什么 Z_n 恰好在 n 为素数时是域的原因。

元素的乘法阶是什么？

单位 a 的乘法阶是使得 a^k 在环中等于 1 的最小正整数 k。根据拉格朗日定理，该阶整除乘法群的大小：对于 Z_n 是 φ(n)，对于 GF(p^k) 是 p^k − 1。阶等于整个群大小的元素称为本原根或生成元。

GF(p^k) 的本原元有什么作用？

本原元是乘法群 GF(p^k)* 的生成元，该群是阶为 p^k − 1 的循环群。域中的每个非零元素都可以写成本原元的幂，这使得离散对数、BCH 码和 Reed-Solomon 纠错成为可能。

延伸阅读

• 模算术 — 维基百科
• 有限域 — 维基百科
• 模 n 的本原根 — 维基百科
• 欧拉函数 — 维基百科
• 不可约多项式 — 维基百科