【算法】如何求原根

请注意,本文编写于 134 天前,最后修改于 49 天前,其中某些信息可能已经过时。

如果一个数 $g$ 在模 $p$ 意义下有 $g^i\not\equiv g^j \pmod p(1\leq i<j \leq p-1)$ ,那么 $g$ 是 $p$ 的原根,其模 $p$ 意义下的幂对应了 $[1,p-1]$ 的每一个数

若存在 $g^i\equiv g^j \pmod p(1\leq i<j \leq p-1)$,则 $g^{j-i}\equiv 1\pmod p$

由欧拉定理得若 $gcd(g,p)=1$,则 $g^{\phi(p)}\equiv 1\pmod p$

显然的 $j-i|phi(p)$ ,所以我们只需要检查 $g^{d}\equiv1\pmod p\ (d|\phi(p))$
若 $g^d\equiv1\pmod p$,则有 $g^{kd}\equiv 1 \pmod p$

那么只需要枚举 $\phi(p)$ 的所有质因子 $pri$,然后检查 $g^{\frac{\phi(p)}{pri}}$ 即可

#include <bits/stdc++.h>
using namespace std;
int n , m;
const int N = 40010;
int pri[N] , tot;
int pf[N] , cnt;
int phi[N];
bool np[N];
int read() {
    int ans = 0 , flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
void getPrime() {
    for(int i = 2 ; i < N ; ++ i) {
        if(!np[i]) pri[++ tot] = i;
        for(int j = 1 ; j <= tot && i * pri[j] < N ; ++ j) {
            np[i * pri[j]] = 1;
            if(i % pri[j] == 0) break;
        }
    }
}
void getPrimeFactor(int x) {
    while(cnt) pf[cnt --] = 0;
    for(int i = 1 ; i <= tot && i <= x ; ++ i) {
        if(x % pri[i] == 0) {
            while(x % pri[i] == 0) x /= pri[i];
            pf[++ cnt] = pri[i];
        }
    }
    if(x != 1) pf[++ cnt] = x;
}
int qpow(int a , int b , int p) {
    int ans = 1;
    while(b) {
        if(b & 1) ans = 1ll * ans * a % p;
        a = 1ll * a * a % p;
        b >>= 1;
    }
    return ans;
}
int getPhi(int x) {
    getPrimeFactor(x);
    int ans = 1;
    for(int i = 1 ; i <= cnt ; ++ i) {
        ans *= (pf[i] - 1); x /= pf[i];
        while(x % pf[i] == 0) {x /= pf[i]; ans *= pf[i];}
    }
    return ans;
}
bool check(int x , int y , int z) {
    bool flag = 1;
    for(int i = 1 ; i <= cnt && flag ; ++ i)
        if(qpow(x , y / pf[i] , z) == 1)
            flag = 0;
    return flag;
}
int main() {
    int p = read();
    getPrime();
    int phi = getPhi(p);
    getPrimeFactor(phi);
    for(int i = 2 ; ; ++ i)
        if(check(i , phi , p)) {
            printf("%d\n" , i);
            return 0;
        }
    return 0;
}
Comments

添加新评论