大家好，欢迎来到IT知识分享网。
一个数m如果有原根，则其原根个数为phi(phi(m))。特别地，对素数有phi(p)=p-1。
假设g是奇素数p的一个原根，则g^1,g^2,…,g^(p-1)在模p意义下两两不同，且结果恰好为1~p-1，由此可以定义“离散对数”，与连续数学中的对数有异曲同工之妙。
离散对数又叫做“指标”，有指标法则：I(ab)≡I(a)+I(b) (mod p-1)；I(a^k)≡k*I(a) (mod p-1)，由此可以把乘法转化为加法。
指标的求法：
#include<cstdio>
using namespace std;
bool notpri[100005];
int pri[100005],zyz[100005];
typedef long long ll;
void Shai(int N){
notpri[1]=1;
for(int i=2;i<=N;++i){
if(!notpri[i]){
pri[++pri[0]]=i;
}
for(int j=1;j<=pri[0] && (ll)i*(ll)pri[j]<=N;++j){
notpri[i*pri[j]]=1;
if(i%pri[j]==0){
break;
}
}
}
}
ll Quick_Pow(ll x,ll p,ll mod){
if(!p){
return 1ll;
}
ll res=Quick_Pow(x,p>>1,mod);
res=res*res%mod;
if((p&1ll)==1ll){
res=(x%mod*res)%mod;
}
return res;
}
int FindRoot(int x){/*求素奇数的最小原根，倘若x不是奇数，但是也有原根的话，将质
因子分解改成对phi(x)即可。倘若要求多个原根，直接接着暴力验证即可*/
int tmp=x-1;
for(int i=1;tmp && i<=pri[0];++i){
if(tmp%pri[i]==0){
zyz[++zyz[0]]=pri[i];
while(tmp%pri[i]==0){
tmp/=pri[i];
}
}
}
for(int g=2;g<=x-1;++g){
bool flag=1;
for(int i=1;i<=zyz[0];++i){
if(Quick_Pow((ll)g,(ll)((x-1)/zyz[i]),(ll)x)==1ll){
flag=0;
break;
}
}
if(flag){
return g;
}
}
}
int main(){
Shai(100000);
printf("%d\n",FindRoot(2017));
return 0;
}
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/31356.html
