数论基础之原根

目录
  1. 1. 什么是原根
    1. 1.1. 阶
  2. 2. 如何求原根
    1. 2.1. 算法原理
    2. 2.2. 程序实现
  3. 3. 哪些数有原根

什么是原根

对于正整数 $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\hskip -1em\mod B,B)=1$。
所以，$\big\lbrace g^0,g^1,\cdots,g^{\varphi(N)-1}\big\rbrace$ 构成 $N$ 的一个既约剩余系。

阶

如果正整数 $X$ 和 $N$ 互质，且 $r$ 为使得 $\displaystyle X^r\equiv 1\hskip -1em\mod N$ 的最小正整数，
则称 $r$ 为 $X$ 模 $N$ 的阶，记做 $\displaystyle \delta_N(X)=r$。

所以，原根的定义也可以描述为：$X$ 是模 $N$ 的一个原根的充要条件为 $\varphi(N)=\delta_N(X)$。

如何求原根

【性质 1】 $r \mid \varphi(N)$
$\hskip 1em$【证】
$\hskip 3em$ 由定义可知，$\varphi(N) \geqslant \delta_N(X)=r$；不妨设 $\varphi(N)=k\cdot r+t$，其中 $0\leqslant t < r$。
$\hskip 3em$ 因为 $\displaystyle X^r\equiv 1\hskip -1em\mod N$，所以，$\displaystyle X^t\equiv X^{k\cdot r+t}\equiv X^{\varphi(N)}\equiv 1\hskip -1em\mod N$；
$\hskip 3em$ 由于，$\displaystyle \delta_N(X)=r$；所以，必有 $t=0$。
$\hskip 3em$ 故 $r \mid \varphi(N)$。
$\hskip 1em$【证毕】

算法原理

据说只要枚举 $X$ 是否 $N$ 的原根即可 = =
通过【性质 1】，我们可以简单地通过检查所有的 $n\mid \varphi(N), n\neq \varphi(N)$，是否都有 $\displaystyle X^n\not\equiv 1\hskip -1em\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\hskip -1em\mod N$，那么 $\displaystyle X^{\frac{\varphi(N)}{p_j}}\equiv 1\hskip -1em\mod N$ 也会成立。

程序实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void GetFac(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 GetRoot(int N) {
    vector<int> fac;
    int phin = phi(N);        // phi(N) 返回 N 的欧拉函数值，实现略
    GetFac(phin, fac);
    for(int i=0; i < fac.size(); ++i)
        fac[i] = phin/fac[i];
    for(int g=2; ; ++g) {
        bool flag = true;
        for(int i=0; i < fac.size(); ++i)
            if( ModPower(g, fac[i], N) == 1 ) { // ModPower 返回 g^{fac[i]}%N，实现略
                flag = false;
                break;
            }
        if( flag ) return g;
    }    
}

哪些数有原根

【定理】 $N$ 有原根的充要条件是 $N=2,4,p^k,2\times p^k$。其中， $p$ 为素数。