一、为什么学原根？
Mermaid · 渲染中（下方为源码）
graph TD A[g^k ≡ a mod m] --> B[乘法群->循环群] B --> C[指数转加法] C --> D[NTT/离散对数]
原根把模 m 的乘法群变成循环群，使指数运算可映射为加法（离散对数）：
g^k ≡ a (mod m)。用途：
- 构造离散对数问题（密码学）
- NTT（数论变换）需要模素数原根做单位根
- 简化幂次循环节分析
二、定义
若 gcd(g, m) = 1 且 g 模 m 的阶 ord_m(g) = φ(m)，则称 g 为模 m 的原根。
存在原根的 m：2, 4, p^k, 2p^k（p 为奇素数）。
三、判定与求原根
若 φ(m) = p1^e1 · p2^e2 · …，则 g 是原根当且仅当对所有质因子 pi，
g^(φ(m)/pi) ≢ 1 (mod m)。
long pow(long a, long b, long m) {
long r = 1; a %= m;
while (b > 0) { if ((b & 1) == 1) r = r * a % m; a = a * a % m; b >>= 1; }
return r;
}
int phi(int n) {
int r = n;
for (int i = 2; i * i <= n; i++)
if (n % i == 0) { while (n % i == 0) n /= i; r = r / i * (i - 1); }
if (n > 1) r = r / n * (n - 1);
return r;
}
int primitiveRoot(int m) {
int ph = phi(m);
int tmp = ph;
java.util.ArrayList<Integer> ps = new java.util.ArrayList<>();
for (int i = 2; i * i <= tmp; i++)
if (tmp % i == 0) { ps.add(i); while (tmp % i == 0) tmp /= i; }
for (int g = 1; g < m; g++) {
if (gcd(g, m) != 1) continue;
boolean ok = true;
for (int p : ps) if (pow(g, ph / p, m) == 1) { ok = false; break; }
if (ok) return g;
}
return -1;
}