Elysia Tools
导航
Math & Numbers
查找模 n 的原根：先判断 n 是否属于 {2, 4, p^k, 2p^k}（乘法群为循环群），再给出最小原根及其判别证书（对每个整除 φ(n) 的素数 q 都有 g^(φ/q) ≠ 1）、原根总数 φ(φ(n))，可列出最多 50 个原根，或验证指定候选 g 的阶是否等于 φ(n)。支持 n ≤ 10¹²。
执行
填写表单、运行工具，并在同一页面查看结果。
案例
相关内容
工具使用指南
原根查找器用于计算模 n 的最小原根、原根总数 φ(φ(n)) 并提供判别证书。工具首先检验模数 n 是否满足循环群充要条件（n ∈ {2, 4, p^k, 2p^k}），支持快速枚举最多 50 个原根或单点验证指定候选数 g 的乘法阶，支持最大 n ≤ 10¹² 的数论计算。
背景
正在完成抽象代数作业，需要证明模 23 乘法群为循环群并列出所有生成元。
问题
需要计算 φ(23)、最小原根以及该素数下的所有原根列表。
如何使用
在模数 n 输入 23，输出模式选择“同时列出原根（最多 50 个）”，运行查找。
n=23, mode=list结果
输出最小原根 g=5 及证书 5^11 ≡ 22 ≢ 1, 5^2 ≡ 2 ≢ 1 (mod 23)，并列出全部 10 个原根：5, 7, 10, 11, 14, 15, 17, 19, 20, 21。
背景
在测试离散对数实现时，需要确认底数 2 是否可以直接作为模 41 的群生成元。
问题
快速检验指定候选数 g=2 的乘法阶是否达到 φ(41)=40。
如何使用
在模数 n 输入 41，输出模式选择“验证候选原根 g”，在候选 g 输入 2 并运行。
n=41, mode=verify, g=2结果
输出显示 2^(40/2) = 2^20 ≡ 1 (mod 41)，素因子 q=2 判定失败，证明 2 的阶仅为 20，不是模 41 的原根。
根据高斯原根定理，仅当模数 n 为 2、4、p^k 或 2p^k（其中 p 为奇素数，k ≥ 1）时，模 n 乘法群才是循环群并存在原根。
若候选数 g 满足与 n 互素，且对 φ(n) 的每个素因子 q 都有 g^(φ(n)/q) ≢ 1 (mod n)，则可严格证明 g 的阶为 φ(n)，即 g 为原根。
如果模 n 存在原根，则模 n 的原根总数精确等于 φ(φ(n))，其中 φ 为欧拉函数。
当选择“同时列出原根”模式时，工具最多列出前 50 个原根，同时会给出原根总数 φ(φ(n))。
支持模数范围为 2 ≤ n ≤ 10¹²。