原根计算器

查找给定模数 n 的所有原根 —— 即乘法群 (Z/nZ)* 的生成元。输入任何正整数即可获取原根、Euler 欧拉函数值、循环群可视化以及带有幂表的逐步验证过程。

原根计算器

原根计算器可找到给定模数 n 的所有原根 —— 即整数 g，其幂 \(g^1, g^2, \ldots, g^{\varphi(n)}\) 能够生成乘法群 \((\mathbb{Z}/n\mathbb{Z})^*\) 的每一个元素。输入任何正整数，即可立即查看所有原根、欧拉函数 \(\varphi(n)\)、交互式循环群可视化、幂表以及最小原根的逐步验证过程。

原根的应用

🔐

Diffie-Hellman

密钥交换协议使用原根作为生成元

🔏

ElGamal 加密

基于离散对数的公钥密码体制

✍

数字签名

DSA 和 Schnorr 签名依赖于循环群生成元

🎲

伪随机数

线性同余生成器使用原根性质

📡

纠错码

Reed-Solomon 和 BCH 码使用有限域的生成元

🧮

数论

指数演算、二次剩余和离散对数问题

关键概念与公式

概念	公式 / 定义	描述
原根	\(\text{ord}_n(g) = \varphi(n)\)	一个整数 g，其模 n 的阶等于欧拉函数值
欧拉函数	\(\varphi(n) = n \prod_{p\|n}\left(1 - \frac{1}{p}\right)\)	[1, n] 中与 n 互质的整数个数
存在准则	\(n \in \{1, 2, 4, p^k, 2p^k\}\)	原根仅对这些形式存在 (p 为奇素数)
原根数量	\(\varphi(\varphi(n))\)	原根存在时的总个数
原根测试	\(g^{\varphi(n)/p} \not\equiv 1 \pmod{n}\) 对于所有素因数 \(p \| \varphi(n)\)	充分条件：只需检查 φ(n) 的素因数
生成所有根	\(g^k \bmod n\) 其中 \(\gcd(k, \varphi(n)) = 1\)	一旦找到一个原根 g，即可得到其他所有原根

理解原根

模 n 的原根是一个整数 g，使得集合 \(\{g^1 \bmod n, g^2 \bmod n, \ldots, g^{\varphi(n)} \bmod n\}\) 等于从 1 到 n-1 中所有与 n 互质的整数构成的集合。在群论术语中，g 是循环乘法群 \((\mathbb{Z}/n\mathbb{Z})^*\) 的一个生成元。例如，3 是模 7 的原根，因为其各次幂 3¹=3, 3²=2, 3³=6, 3⁴=4, 3⁵=5, 3⁶=1 (mod 7) 产生了集合 {1, 2, 3, 4, 5, 6} 中的每一个元素。

原根何时存在？

数论中的一个经典结果（由高斯证明）指出，模 n 的原根存在当且仅当 n 是以下情形之一：1, 2, 4, p^k 或 2p^k，其中 p 是奇素数且 k ≥ 1。对于 n 的其他值，群 \((\mathbb{Z}/n\mathbb{Z})^*\) 不是循环群 —— 根据中国剩余定理，它可以分解为循环群的直积 —— 因此没有单个元素可以生成整个群。例如，\((\mathbb{Z}/8\mathbb{Z})^* \cong \mathbb{Z}/2 \times \mathbb{Z}/2\) 没有原根。

如何高效地寻找原根

标准算法分为两个阶段。阶段 1：通过尝试找到最小的原根。对于从 2 开始的每个候选数 g，计算 \(\varphi(n)\) 的每个素因数 p 的 \(g^{\varphi(n)/p} \bmod n\)。如果这些结果都不等于 1，那么 g 就是一个原根。在实践中，最小原根通常很小 —— 猜想对于任何 \(\epsilon > 0\)，它都是 \(O(n^\epsilon)\)。阶段 2：一旦已知一个原根 g，所有其他原根就是 \(g^k \bmod n\)，其中 \(\gcd(k, \varphi(n)) = 1\)，总共恰好有 \(\varphi(\varphi(n))\) 个原根。

如何使用原根计算器

输入模数 n：在输入框中输入一个正整数，或点击快速示例按钮之一来自动填充数值。
点击“查找原根”：按下按钮计算模 n 的所有原根。
查看结果：查看原根的数量、完整列表、欧拉函数、群阶以及您的 n 是否存在原根。
探索可视化图：对于 n ≤ 100，交互式循环群轮状图显示了每个原根如何通过其幂生成整个群。点击任何原根芯片即可在轮状图上查看其循环路径。
研究幂表：网格显示了 k = 1, 2, …, φ(n) 的 g^k mod n，其中原根和单位元以不同的颜色突出显示。

密码学中的原根

原根在现代密码学中起着核心作用。在 Diffie-Hellman 密钥交换中，双方协商一个大素数 p 和模 p 的一个原根 g，然后交换公钥 g^a mod p 和 g^b mod p。共享密钥 g^ab mod p 对窃听者来说在计算上是不可行的，因为在大型循环群中计算离散对数被认为是困难的。同样，ElGamal 加密和数字签名算法 (DSA) 都依赖于由原根生成的群中离散对数问题的难度。

常见问题解答

什么是模 n 的原根？

模 n 的原根是一个整数 g，使得 g¹、g²、…、g^φ(n) 模 n 的幂正好产生每一个与 n 互质的整数一次。等价地，g 的乘法阶等于 φ(n)，意味着 g 生成了整个乘法群 (Z/nZ)*。

对于哪些 n 值存在原根？

原根存在的充要条件是 n 为 1, 2, 4, p^k 或 2p^k，其中 p 是奇素数，k 是正整数。例如，n = 7（素数）、n = 9 (3²) 和 n = 14 (2 × 7) 都有原根，但 n = 8, n = 12 和 n = 15 则没有。

n 有多少个原根？

如果 n 存在原根，那么模 n 的原根数量等于 φ(φ(n))，其中 φ 是欧拉函数。例如，n = 7 有 φ(φ(7)) = φ(6) = 2 个原根，分别是 3 和 5。

如何找到原根？

寻找 n 的原根：首先计算 φ(n) 并进行因式分解。然后对于每个与 n 互质的候选数 g，检查对于 φ(n) 的每个素因数 p，g^(φ(n)/p) 是否不模 n 同余于 1。如果所有检查都通过，则 g 是一个原根。所有其他根可以通过 g^k mod n 找到，其中 gcd(k, φ(n)) = 1。

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

原根是 Diffie-Hellman 密钥交换、ElGamal 加密和数字签名算法的基础。它们确保了离散对数问题的难度，这是这些加密协议安全性的基础。原根生成群的所有元素，最大限度地扩大了攻击者的搜索空间。

引用此内容、页面或工具为：

"原根计算器" 于 https://MiniWebtool.com/zh-cn/原根计算器/，来自 MiniWebtool，https://MiniWebtool.com/

由 MiniWebtool 团队。更新日期：2026-04-16

您还可以尝试我们的 AI数学解题器 GPT，通过自然语言问答解决您的数学问题。

其他相关工具:

原根计算器