自 2010 年 · 每月支持超过 200 万次工具运行
自 2010 年
添加到 Chrome

我的工具箱

自动模式

还没有收藏的工具。

升级为高级版
相关工具
复数计算器模乘逆元计算器多项式根计算器与详细步骤环与域计算器群论阶数计算器欧拉函数计算器
主页 > 数学 > 进阶数学计算
 

原根计算器

求模n的所有原根,即乘法群的生成元。输入任意正整数即得原根列表、欧拉函数值、循环群可视化,以及带幂次表的分步验证过程。

免费使用无需注册即时出结果
原根计算器立即免费试用 ▼
示例：
原根存在的条件为 n = 1, 2, 4, pk, 或 2pk (p 为奇素数)

Embed 原根计算器 Widget

原根计算器

原根计算器可找到给定模数 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, pk 或 2pk，其中 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))\) 个原根。

如何使用原根计算器

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

密码学中的原根

原根在现代密码学中起着核心作用。在 Diffie-Hellman 密钥交换中，双方协商一个大素数 p 和模 p 的一个原根 g，然后交换公钥 ga mod p 和 gb mod p。共享密钥 gab 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

开发者 API 可用: 用一次 JSON HTTP 请求，把这个工具接入你的应用、自动化流程或智能体。 查看 API 文档

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

进阶数学计算:

热门与最新工具:

有理根定理计算器立方根计算器数字根计算器查看全部 →
主页 > 数学 > 进阶数学计算 > 原根计算器