Primitive-Roots-Rechner

原理

g 是模素数 p 的原根，指 g 的幂恰好跑遍模 p 的全部非零剩余（即 1 到 p−1 各一次），也就是 g 的阶（乘法周期）等于 p−1。判据：对 p−1 的每个素因子 q，都有 g^((p−1)/q) ≢ 1 (mod p)。原根个数恰为 φ(p−1)——本工具对每个候选 g 逐一验证该判据。

原根让离散对数变得自然：任何非零剩余都可写成 g^k， Diffie-Hellman 密钥交换与 ElGamal 签名都建立在「由 g^k 反推 k 很难」之上。不是所有模数都有原根：恰有原根的模数是 2、4、p^k、2p^k。

使用步骤

① 输入素数 p；② 得到全部原根、个数 φ(p−1) 与最小原根；③ 密码学应用通常直接取最小原根为生成元。

计算示例

p = 7：原根 3 与 5（φ(6) = 2 个）；p = 11：原根 2、6、7、8（4 个）；p = 13：原根 2、6、7、11；p = 97 的最小原根是 5。3^2 = 2、3^3 = 6、3^6 = 1 (mod 7)——阶恰为 6，故 3 是原根。

注意事项

p−1 的素因子分解是判据的前提（本工具内部枚举 q 验证）；对大素数应先分解 p−1 再检验。合数模的「原根」定义相同但存在性需先查 2、4、p^k、2p^k 列表。

常见问题

Q：原根为什么总是成组出现？A：若 g 是原根，g^k 与 p 互素当且仅当 gcd(k, p−1) = 1，这样的 k 有 φ(p−1) 个，故原根成 φ(p−1) 个并可与指数一一对应。

Q：Artin 猜想和它有关吗？A：有关——Artin 常数猜想：对固定整数 a 非完全平方，a 是无穷多个素数的最小原根，密度约 0.3739。