数论基础之原根
什么是原根
¶原根的定义
对于正整数 $N$，如果正整数 $g$ 满足 $\gcd(g,N)=1$ 且 $\big\lbrace g^0,g^1, \cdots,g^{\varphi(N)-1}\big\rbrace$ 两两模 $N$ 不同余，则称 $g$ 为 $N$ 的一个原根。
由于 $\displaystyle \gcd(A,B)=1 ~\Leftrightarrow~ \gcd(A \mod B,B)=1$。所以，$\big\lbrace g^0,g^1,\cdots,g^{\varphi(N)-1}\big\rbrace$ 构成 $N$ 的一个既约剩余系。
原根的阶
如果正整数 $X$ 和 $N$ 互质，且 $r$ 为使得 $X^r\equiv 1 \mod N$ 成立的最小正整数，则称 $r$ 为 $X$ 模 $N$ 的阶，记做 $\delta_N(X)=r$.
所以，原根的定义也可以描述为：$X$ 是模 $N$ 的一个原根的充要条件为 $\varphi(N)=\delta_N(X)$.
如何求原根
¶【性质1】：$r \mid \varphi(N)$
由定义可知，$\varphi(N) \geqslant \delta_N(X)=r$；不妨设 $\varphi(N)=k\cdot r+t$，其中 $0\leqslant t < r$.
因为 $X^r\equiv 1\mod N$，所以有 $X^{\varphi(N)} \equiv X^{k\cdot r+t} \equiv X^t \equiv 1 \mod N$.
由于 $\delta_N(X)=r$；所以，必有 $t=0$.
故 $r \mid \varphi(N)$.
算法原理
¶枚举 $X$ 是否 $N$ 的原根即可。
通过【性质 1】，我们可以简单地通过检查所有的 $\displaystyle \left\lbrace n \Big| 1 < n < \varphi(N) \;\text{且}\; n\mid \varphi(N) \right\rbrace$ 是否都满足 $X^n\not\equiv 1 \mod N$ 来判断 $X$ 是否为模 $N$ 的一个原根。进一步地，如果 $\varphi(N)=p_1^{k_1}p_2^{k_2}\cdots p_s^{k_s}$，我们仅需检查 $\displaystyle n=\frac{\varphi(N)}{p_i},1\leqslant i\leqslant s$ 就够了。原因很简单，如果 $\forall i, \; 1\leqslant i\leqslant s$ 都有 $0\leqslant a_i\leqslant k_i$ 成立，且 $\exists j ,\; 1\leqslant j\leqslant s$ 使得 $0\leqslant a_j < k_j$ 成立；则必有 $\displaystyle p_1^{a_1}p_2^{a_2}\cdots p_s^{a_s} \mid \frac{\varphi(N)}{p_j}$ 成立。所以，若 $\displaystyle X^{p_1^{a_1}p_2^{a_2}\cdots p_s^{a_s}}\equiv 1 \mod N$，那么 $\displaystyle X^{\frac{\varphi(N)}{p_j}}\equiv 1 \mod N$ 也会成立。
综上，对于每个数 $g$，最多检查 $\varphi(N)$ 的素因子个数次即可判断其是否为 $N$ 的一个原根。
程序实现
¶12345678910111213141516171819202122232425262728293031void calcFactor(int N, vector<int>& fac) { int sm = ceil(sqrt(1.0 * N)); for (int i = 2; i <= sm; ++i) { if (N%i == 0) { fac.push_back(i); while (N%i == 0) N /= i; } } if (N > 1) fac.push_back(N);}
int calcPrimitiveRoot(int N) { vector<int> fac;
// phi(N) 返回 N 的欧拉函数值，实现略 int PHI_N = phi(N); calcFactor(PHI_N, fac);
for (int i = 0; i < fac.size(); ++i) fac[i] = PHI_N / fac[i]; for (int g = 2; ; ++g) { bool flag = true; for (int i = 0; i < fac.size(); ++i) { // powerMod 返回 $g^{fac[i]} \mod N$，实现略 if (powerMod(g, fac[i], N) == 1) { flag = false; break; } } if (flag) return g; } }
小记
¶哪些数有原根
$N$ 有原根的充要条件是 $N=2,4,p^k,2\times p^k$。其中，$p$ 为奇素数，$k$ 为任意正整数。