如何找原根_原根怎么找-CSDN博客

什么是原根

一个数a，如果他是p的一个原根
也就是a要满足
$a^x$在$modp$的意义下可以取得$0$~$(p-1)$的所有数

怎么找

这里提供一个找p是质数的方法
就是直接暴力枚举a
判断的话，就是没有所有(p-1)的因数x
然后看一下$a^{\frac{p-1}{x}}$在$mod p$的意义下是不是1
如果不是。那么就是一个原根
否则就不是原根
CODE:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
LL pri[105],cnt=0;
void div (LL n)
{
    for (LL u=2;u*u<=n;u++)
        if (n%u==0)
        {
            pri[++cnt]=u;
            while (n%u==0) n/=u;
        }
}
LL n;
LL pow (LL x,LL y)
{
    if (y==1) return x;
    LL lalal=pow(x,y>>1);
    lalal=lalal*lalal%n;
    if (y&1) lalal=lalal*x%n;
    return lalal;
}
int main()
{
    scanf("%lld",&n);
    div(n-1);
//  for (int u=1;u<=cnt;u++)    printf("%d ",pri[u]);
    for (LL u=2;;u++)
    {
        bool tf=true;
        for (LL i=1;i<=cnt;i++)
        {
            LL t=(n-1)/pri[i];
            if (pow(u,t)==1)
            {
                tf=false;
                break;
            }
        }
        if (tf)
        {
            printf("%lld\n",u);
            break;
        }
    }
    return 0;
}