原根计算器

g 是模 p 的原根：g 的幂 g¹, g², …, g^(p−1) 恰好遍历 1~p−1 所有非零剩余——g 单人生成了整个乘法群。模 7 的最小原根是 3：3¹=3, 3²=2, 3³=6, 3⁴=4, 3⁵=5, 3⁶=1，一个不漏。

原根是离散对数问题的基石：已知 g^x mod p 反求 x 极难（大素数时），这个「单向性」撑起了 Diffie-Hellman 密钥交换与 ElGamal 加密——你每次 HTTPS 连接都在用原根。

原根的存在性是数论中「结构性惊喜」的代表：并非每个模数都有原根——高斯证明，只有 1、2、4、p^k 和 2p^k（p 为奇素数）这些模数存在原根。模 8 就没有原根：每个奇数的平方都 ≡1 (mod 8)，没有任何元素能生成整个群。这个「存在性定理」的深层含义是：乘法群 (Z/nZ)* 为循环群的充要条件，就是 n 属于上述清单。

检验算法的高效性来自一个精巧的约简：验证 g 是原根，不需要逐一计算 g 的 p−1 个幂次，只需对 p−1 的每个素因子 q 检查 g^((p−1)/q) ≢ 1——因为阶必须整除 p−1，若阶是真因子，必然缺失某个素因子的「满次数」。这把检验成本从 O(p) 压到 O(素因子个数 × log p)，配合快速幂模运算，万级素数毫秒出结果。相关工具见欧拉函数计算器与模幂计算器。

原根的现代舞台远超纯数学：Diffie-Hellman 密钥交换选择大素数 p 的原根 g，双方交换 g^a mod p 与 g^b mod p 即可协商共享密钥 g^(ab)，窃听者面临离散对数难题；快速数论变换（NTT）用原根构造单位根，把多项式乘法压到 O(n log n)，是格密码与同态加密的引擎；里德-所罗门纠错码的生成多项式同样扎根于原根构造的循环群。