原根计算器
使用 MiniWebtool 的原根计算器，探索模整数乘法循环。若原根存在，工具会找出原根并报告欧拉函数值，同时以幂表和循环群图说明生成的余数。
不确定怎么使用？问问 AI
你的广告拦截器导致我们无法展示广告
MiniWebtool 依靠广告收入免费提供服务。如果这个工具帮到了你，欢迎升级获得无广告浏览和更多每日使用次数，或将 MiniWebtool.com 加入白名单后刷新页面。
- 允许 MiniWebtool.com 显示广告，然后刷新
- 或升级获得无广告浏览和更高每日额度
原根计算器
原根计算器可找到给定模数 n 的所有原根 —— 即整数 g，其幂 \(g^1, g^2, \ldots, g^{\varphi(n)}\) 能够生成乘法群 \((\mathbb{Z}/n\mathbb{Z})^*\) 的每一个元素。输入任何正整数，即可立即查看所有原根、欧拉函数 \(\varphi(n)\)、交互式循环群可视化、幂表以及最小原根的逐步验证过程。
功能概览
原根计算器列出正整数模数n的所有原根，并给出欧拉函数值。它还显示幂表、小模数的循环群轮盘，以及最小原根的验证过程。
| 功能 | 具体内容 | 适用场景 |
|---|---|---|
| 模数输入 | 输入任意正整数n，或使用示例按钮选择n = 7、13、9、14、12和97。 | 探索原根是否存在与n的关系 |
| 全部原根 | 列出所有原根、原根个数以及群的阶。若不存在原根（如n = 12），页面会予以说明。 | 数论练习和密码学示例 |
| 欧拉函数 | 给出 phi(n)；原根存在时，其个数为 phi(phi(n))。 | 用公式核对原根个数 |
| 循环群轮盘 | 对于n不超过100的情况，可交互的轮盘动画展示所选原根如何通过其幂次生成模n的全部单位。 | 直观看到生成元如何遍历群中的元素 |
| 幂表 | 表格显示 k = 1 至 phi(n) 时的 g^k mod n，并高亮原根和单位元。 | 通过观察验证某个原根 |
| 验证步骤 | 逐步演示对最小原根的检验过程。 | 学习如何利用phi(n)的质因数进行检验 |
原根的应用
关键概念与公式
| 概念 | 公式 / 定义 | 描述 |
|---|---|---|
| 原根 | \(\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))\) 个原根。
如何使用原根计算器
- 输入模数 n：在输入框中输入一个正整数，或点击快速示例按钮之一来自动填充数值。
- 点击“查找原根”：按下按钮计算模 n 的所有原根。
- 查看结果：查看原根的数量、完整列表、欧拉函数、群阶以及您的 n 是否存在原根。
- 探索可视化图：对于 n ≤ 100，交互式循环群轮状图显示了每个原根如何通过其幂生成整个群。点击任何原根芯片即可在轮状图上查看其循环路径。
- 研究幂表：网格显示了 k = 1, 2, …, φ(n) 的 g^k mod n，其中原根和单位元以不同的颜色突出显示。
密码学中的原根
原根在现代密码学中起着核心作用。在 Diffie-Hellman 密钥交换中，双方协商一个大素数 p 和一个大素数阶子群的生成元，该子群的阶 q 整除 p−1，然后交换公钥 ga mod p 和 gb mod p。窃听者在计算上难以求出共享密钥 gab mod p，因为人们认为在大型循环子群中计算离散对数很困难。同样，ElGamal 加密和数字签名算法 (DSA) 都依赖于这些子群中离散对数问题的难度。
常见问题解答
引用此内容、页面或工具为：
"原根计算器" 于 https://MiniWebtool.com/zh-cn/原根计算器/，来自 MiniWebtool，https://MiniWebtool.com/
由 MiniWebtool 团队。更新日期：2026-04-16
与喜欢的 AI 聊聊这个工具
使用 Gemini 时，请将复制的问题粘贴到聊天框。也可以在下方手动复制。
查看提问内容
进阶数学计算:
- 邻接矩阵计算器 新
- antilog计算器
- beta函数计算器
- 二项式系数计算器
- 二项概率分布计算器
- 按位计算器
- 布尔代数化简器 新
- 中央极限定理计算器
- 中国剩余定理计算器
- 组合计算器 热门
- 互补误差函数计算器
- 复数计算器 热门
- 连分数计算器
- 错排 子阶乘计算器
- 迪杰斯特拉最短路径计算器
- 熵计算器
- 误差函数计算器
- 欧拉函数计算器
- 指数衰减计算器（高精度）
- 指数增长计算器 高精度
- 指数积分计算器
- 指数计算器（高精度）
- 扩展欧几里得算法计算器
- 阶乘计算器
- 伽玛功能计算器
- 黄金比例计算器
- 图着色计算器 新
- 图度数序列验证器
- 群论阶数计算器 新
- 半衰期计算器
- 哈密顿路径检查器 新
- 容斥原理计算器 新
- 卡诺图 (K-Map) 求解器 新
- 线性规划求解器 新
- 马尔可夫链稳态分布计算器
- 最小生成树计算器
- 模幂运算计算器 新
- 模乘逆元计算器
- 负二项分布计算器 新
- 网络最大流计算器 新
- 百分比增长率计算器
- 排列计算器
- 重复排列计算器 新
- 鸽巢原理计算器
- 平面图检查器 新
- 泊松分布计算器
- 多项式根计算器与详细步骤
- 原根计算器
- 概率计算器
- 概率分布计算器
- 比例计算器 热门
- 二次公式计算器 热门
- 环与域计算器 新
- 四舍五入计算器 新
- 科学计算器
- 科学记数法计算器 热门
- 集合论计算器
- 有效数字计算器 新
- 稳定婚姻问题求解器 新
- 斯特林数计算器
- 立方和计算器
- 连续数之和计算器
- 平方和计算器
- 拓扑排序计算器 新
- 旅行商问题求解器 TSP 新
- 真值表生成器
- 韦恩图生成器3集合