浅谈阶与原根

阶

阶的定义：若a,p均为正整数，且gcd(a,p)=1,称满足(mod p)的最小正整数r为a模p的阶，记作.

定义枯燥乏味，举个栗子，如a=3，p=7，根据暴力递推我们可以得到这样一张有向有环图

 注意：这不是特例，再举个栗子，如a=2，p=7，可以得到

 其中节点的编号即为出现的模数

根据欧拉定理可知，当gcd(a,p)=1,a>0,p>0,p为素数时一定有(mod p)，再根据阶的定义，一定有阶r | ,这说明在这张图上走步一定会回到原点，但没有保证的是这步一定是把这个环走了一遍，也可能走了两遍...n遍，所以这个环的长度一定是的因子，那求阶可能想到的一种做法就是去枚举的所有因子，看最小的a的幂次模p等于1是什么时候，但这并不是最好的做法。

假设阶是d，(mod p),那么d | x，又知道欧拉定理是(mod p)， 根据唯一分解定理分解=,先令d=,枚举的每个质因子，当d%==0并且ad/pi" role="presentation">ad/pi$a^{d/p_i}$时，d/=，否则什么都不做，这说明的是此时的对于d来说相当于对着环走了次，最后虽然也是回到了原点，但并不是环的长度，所以要除掉，如果d/后取模不是1了说明回不到原点，因此这个因子是关键的，不能除掉。综上所述，假设环的长度为L,除掉的相当于n*L中的n的因子，这里力求的是L的长度，所以要使得n为1，因此枚举所有的的因子。

还有一个前置小芝士:为1到p-1中与p互质的正整数的个数，显而易见素数的欧拉函数的值为p-1

求阶代码:

#include 
using namespace std;
using LL = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int a, p;//底数和模数
    cin >> a >> p;
    function qp = [&](LL a, LL b) {
        LL res = 1;
        for (; b; b >>= 1, a = a * a % p) {
            if (b & 1) {
                res = res * a % p;
            }
        }
        return res % p;
    };
    int d = p - 1, m = p - 1;
    vector<int> z;
    for (int i = 2; i * i <= m; i++) {
        if (m % i == 0) {
            z.push_back(i);
            while (m % i == 0) {
                m /= i;
            }
        }
    }
    if (m != 1) {//如果还剩下一个没取到的素数还要把它放进因子集合里
        z.push_back(m);
    }
    int len = z.size();
    for (int i = 0; i < len; i++) {
        while (d % z[i] == 0 and qp(a, d / z[i]) == 1) {
            d /= z[i];
        }
    }
    cout << d << '\n';//阶
    return 0;
}

原根

原根的定义：如果g(mod m)的阶为,那么g就是m的原根。

原根就是特殊情况的阶。

构成了模m的简化剩余系。

只有1，2，4，存在原根(p为奇素数 (奇素数：除2以外的素数) )。

注意：2的幂次可能是没有原根的

结论1：原根很多

结论2：最小的原根不会很大且2到p-1之间随机分布

如何判断一个数g是否是原根？

类比于求阶的计算，设模数m，枚举的所有因子，如果所有(mod m)，那么g就是原根，否则不是原根，即阶可以变得更小，所以阶不等于

注意：如果a是p的原根，a不一定是的原根，如果a是的原根，那么一定是更高次的原根

如果g是m的原根，那么循环节里一定会出现1到m之间与m互质的数，都可以表示成其中(i>=0,i<) (简化剩余系)

根据上述的结论2可知，求解原根的时候可以从1开始暴力往上计算。

求解原根代码:

#include 
using namespace std;
using LL = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int p;//求解素数p的原根
    cin >> p;
    function qp = [&](LL a, LL b) {
        LL res = 1;
        for (; b; b >>= 1, a = a * a % p) {
            if (b & 1) {
                res = res * a % p;
            }
        }
        return res % p;
    };
    vector<int> z;//因子集合
    int m = p - 1;
    for (int i = 2; i * i <= m; i++) {
        if (m % i == 0) {
            z.push_back(i);
            while (m % i == 0) {
                m /= i;
            }
        }
    }
    if (m != 1) {//还有素数没有除完
        z.push_back(m);
    }
    int len = z.size();
    for (int g = 1; g < p; g++) {
        bool ok = true;
        for (int i = 0; i < len; i++) {
            if (qp(g, (p - 1) / z[i]) == 1) {//阶可以更小,因此不是原根
                ok = false;
                break;
            }
        }
        if (ok) {
            cout << g << '\n';
            exit(0);
        }
    }
    //否则没有原根
    return 0;
}