原根计算器

欢迎使用原根计算器，这是一个功能强大的免费在线工具，可以查找任何正整数 n 的所有模原根。此计算器提供逐步验证、幂表和动画循环群可视化，帮助您理解原根如何生成乘法群。无论您是在学习数论、准备密码学考试，还是在竞赛编程中处理模算术，该工具都能提供即时、准确的结果和教育见解。

什么是原根？

模 n 的原根是一个整数 g，其幂生成所有与 n 互质的整数。形式上，如果 g 模 n 的乘法阶等于欧拉函数 \(\varphi(n)\)，则 g 是模 n 的原根。这意味着集合

包含了 1 到 n-1 之间所有与 n 互质的 \(\varphi(n)\) 个整数。原根本质上是循环群 \((\mathbb{Z}/n\mathbb{Z})^*\) 的生成元。

快速示例

考虑 n = 7。由于 7 是素数，\(\varphi(7) = 6\)。让我们检查 g = 3 是否为原根：

• 3¹ mod 7 = 3
• 3² mod 7 = 2
• 3³ mod 7 = 6
• 3⁴ mod 7 = 4
• 3⁵ mod 7 = 5
• 3⁶ mod 7 = 1

其幂产生 {3, 2, 6, 4, 5, 1} = {1, 2, 3, 4, 5, 6}，这是所有与 7 互质的整数。因此，3 是模 7 的原根。

何时存在原根？

模 n 的原根存在当且仅当 n 是以下形式之一：

• n = 1, 2, 或 4
• n = p^k 其中 p 是奇素数且 k ≥ 1
• n = 2p^k 其中 p 是奇素数且 k ≥ 1

例如，7, 9, 11, 13, 14, 18, 23, 25, 27, 46 存在原根，但 8, 12, 15, 16, 20, 21, 24 不存在。

如何查找原根

1. 输入模数：在输入框中输入一个正整数 n（从 2 到 100,000）。
2. 计算：点击“查找原根”或按回车键。
3. 查看所有原根：查看完整的原根列表，以及欧拉函数和统计数据。
4. 研究幂表：检查最小原根如何生成所有互质剩余。
5. 可视化循环群：对于小模数，查看显示循环结构的动画轮状图。

n 有多少个原根？

如果模 n 存在原根，则其数量等于：

例如，对于 n = 13：\(\varphi(13) = 12\) 且 \(\varphi(12) = 4\)，因此模 13 恰好有 4 个原根（分别是 2, 6, 7, 11）。

验证算法

高效检查 g 是否为模 n 的原根的方法：

1. 使用 n 的质因数分解计算 \(\varphi(n)\)
2. 找到 \(\varphi(n)\) 的所有互异质因数 \(p_1, p_2, \ldots, p_k\)
3. 对于每个质因数 \(p_i\)，检查：\(g^{\varphi(n)/p_i} \not\equiv 1 \pmod{n}\)
4. 如果所有检查都通过，则 g 是原根

这种方法比计算 g 的所有幂要快得多，因为我们只需要测试 \(k\) 个幂运算，而不是 \(\varphi(n)\) 个。

密码学中的原根

Diffie-Hellman 密钥交换

Diffie-Hellman 协议使用大素数 p 和模 p 的原根 g。Alice 选择私钥 a，发送 \(g^a \bmod p\)。Bob 选择私钥 b，发送 \(g^b \bmod p\)。双方计算共享密钥 \(g^{ab} \bmod p\)。安全性依赖于离散对数问题在计算上的困难性。

ElGamal 加密

ElGamal 同样使用原根作为生成元。公钥是 \((p, g, g^x \bmod p)\)，其中 x 是私有的。g 生成所有元素的事实确保了每条消息都可以被加密。

数字签名

DSA（数字签名算法）及相关方案使用 \((\mathbb{Z}/p\mathbb{Z})^*\) 子群中的原根来创建和验证数字签名。

参考表：最小原根

常见问题解答

什么是模 n 的原根？

模 n 的原根是一个整数 g，使得幂 \(g^1, g^2, \ldots, g^{\varphi(n)}\) 模 n 时产生所有与 n 互质的整数。换句话说， g 生成了整个乘法群 \((\mathbb{Z}/n\mathbb{Z})^*\)。g 模 n 的阶等于欧拉函数 \(\varphi(n)\)。

对于哪些 n 值存在原根？

模 n 存在原根当且仅当 n 为 1, 2, 4, p^k 或 2p^k，其中 p 是奇素数且 k ≥ 1。例如， n = 7（素数）、 n = 9 (3²)、 n = 14 (2×7) 存在原根，但 n = 8, 12, 15 或 16 不存在。

n 有多少个原根？

如果模 n 存在原根，原根的数量等于 \(\varphi(\varphi(n))\)，其中 \(\varphi\) 是欧拉函数。例如，对于 n = 13（素数），\(\varphi(13) = 12\) 且 \(\varphi(12) = 4\)，因此模 13 恰好有 4 个原根。

为什么原根在密码学中很重要？

原根是 Diffie-Hellman 密钥交换协议和 ElGamal 加密系统的基础。在这些加密协议中，模大素数 p 的原根 g 被用作生成元。其安全性依赖于离散对数问题的困难性：给定 \(g^x \bmod p\)，计算上很难找到 x。

如何验证 g 是模 n 的原根？

验证 g 是模 n 的原根：(1) 计算 \(\varphi(n)\)。(2) 找到 \(\varphi(n)\) 的所有质因数 \(p_1, p_2, \ldots, p_k\)。(3) 检查对于每个质因数 \(p_i\)，\(g^{\varphi(n)/p_i} \not\equiv 1 \pmod{n}\)。如果所有检查都通过，则 g 是原根。这比计算 g 的所有幂要快得多。

相关工具