1、原根的定义：
原根，是一个数学符号。设m是正整数，a是整数，若a模m的阶等于φ（m）（m的欧拉函数），则称a为模m的一个原根。
阶：a和模m互质，使ad ≡1（mod m）成立的最小正整数d称为a对模m的阶。例如：22≡1（mod3），2对模3的阶为2。
假设一个数g对于P来说是原根，那么gi mod p的结果两两不同，且有 1 < g < P , 0 < i < P.那么g可以称为是P的一个原根。
归根到底就是 gP-1 ≡ 1 (mod P)当且仅当质数为P-1的时候成立（P为素数）.
求原根目前的做法只能是从2开始枚举，然后暴力判断g^(P-1) = 1 (mod P)是否当且当指数为P-1的时候成立，而由于原根一般都不大，所以可以暴力得到。
2、原根的性质：
（1）可以证明，如果正整数（a，m） = 1 和正整数d满足ad ≡ 1（mod 7），则d整除φ（m）。因此Ordm（a）整除φ（m）。在例子中，
当a = 3 时，我们仅需要验证3的1、2、3和6次方模7的余数即可。
（2）记 δ = Ordm（a），则a1 ，…. aδ-1 构成模m的简化剩余系数。
（3）模m有原根的充要条件是m = 1，2 ， 4 , p , 2p , pn , 其中p是奇质数，n是任意正整数。
（4）对正整数（a，m）= 1 ， 如果a是模m的原根，那么a是整数n乘法群（即加法群 Z/mZ的可逆元，也就是所有与 m 互素的正整数构成的等价类构成的乘法群）Zn的一个生成元。由于Zn有φ(m)个元素，而它的生成元的个数就是它的可逆元个数，即φ(φ(m))个，因此当模m有原根时，它有φ(φ(m))个原根
3、求质数最小原根
求质数最小原根：对于质数p，φ（p） = p – 1 ，根据费马小定理，ap-1≡1(mod p) 成立a为大于1的整数。所有只需验证没有比p-1小的数k
使得ak≡1(mod p).
而k不需要全部枚举，只需枚举p-1的质因数即可。（如果x为p-1的质因子，且ax ≡ 1(mod p),那么x的倍数nx显然也满足anx ≡ 1(mod p) ，所有p-1不为a对模p的阶（不是最小），即不是原根）。
素数p（3<=p<=1e9），一般对于要多次分解质因数时，可以先筛选出素数，然后再素数里进行质因数分解。
因为这题只需进行一次，可以不需要筛素数，直接分解O（√n）。
首先求质幂分解Φ（m） = p1e1 * p2e2 * …*pkek
然后枚举g，若恒不满足gΦ(m)/pi ≡ 1 mod(p) 其中i = 1，2….k.
则g是m的原根。
const int maxn = 1e5+9;
const int N = 1e6+9;
int vis[N], prime[maxn] , len , pf[maxn] , len1;
void Erasieve(){
rep(i , 2 , N){
if(!vis[i]){
prime[++len] = i ;
for(int j = i * i ; j <= N ; j += i){
vis[j] = 1 ;
}
}
}
}
void oulasieve(){
rep(i , 2 , N){
if(!vis[i]){
prime[++len] = i ;
}
for(int j = 1 ; j <= len && prime[j] * i <= N ; j++){
vis[prime[j]*i] = 1;
if(i % prime[j] == 0) break;
}
}
}
void divide(int x){
for(int i = 1 ; i <= len && prime[i] * prime[i] <= x; i++){
if(x%prime[i]==0){
pf[++len1] = prime[i];
while(x % prime[i] == 0){
x /= prime[i] ;
}
}
}
if(x > 1) pf[++len1] = x ;
}
/*void divide2(int x){
for(int i = 2 ; i * i <= x ; i++){
if(x % i == 0){
phi[++len1] = i ;
while(x % i == 0) x /= i ;
}
}
}*/
int quickpow(int a , int b , int p){
int ans = 1 ;
while(b){
if(b&1){
ans = ans * a % p ;
}
b >>= 1 ;
a = a * a % p ;
}
return ans ;
}
void solve(){
oulasieve();
int p ;
cin >> p ;
divide(p-1);
rep(i , 2 , p-1){
int flag = 1 ;
rep(j , 1 , len1){
if(quickpow(i , (p-1)/pf[j] , p) == 1){
flag = 0 ;
break;
}
}
if(flag == 1){
cout << i << endl;
break;
}
}
}
今天的文章原根_本原单位根分享到此就结束了，感谢您的阅读，如果确实帮到您，您可以动动手指转发给其他人。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/45604.html
