对于素数 p,如果存在一个正整数 1<a<p,使得 a1,a2,…,ap−1 模 p 的值取遍 1,2,…,p−1 的所有整数,称 a 是 p 的一个原根(primitive root),其实就是循环群的生成元。
如 果 a j ≡ a i ( m o d p ) , 则 i ≡ j ( m o d p − 1 ) 。 这 里 有 两 个 例 子 : 如果 aj≡ai(mod p),则 i≡j(mod p−1)。这里有两个例子:如果aj≡ai(modp),则i≡j(modp−1)。这里有两个例子:
5是7的原根,因为5–>3–>1–>6–>4–>2–>0,然后开始循环
2不是7的原根,因为2–>4–>1–>2–>4…,过早的循环了
如果g是P的原根,就是( g P − 1 ) ≡ 1 ( m o d P ) 当且仅当指数为P-1的时候成立.(这里P是素数).
即 设m是正整数,a是整数,若a模m的阶等于φ(m),则称a为模m的一个原根。
φ(m):这货是欧拉函数
定理:
定理一:
设p是奇素数,则模p的原根存在;
定理二:
设g是模p的原根,则g或者g+p是模的原根;
定理三:
设p是奇素数,则对任意,模的原根存在;
定理四:
设1,则g是模的一个原根,则g与g+中的奇数是模2的一个原根。
性质:
性质一:
对于任意正整数a,m,如果(a,m) = 1,存在最小的正整数 d 满足a^d≡1(mod m),则有 d 整除 φ(m),因此Ordm(a)整除φ(m)。这里的d被称为a模m的阶,记为Ordm(a)。
例如:求3模7的阶时,我们仅需要验证 3 的 1 、2、3 和 6 次方模 7 的余数即可。
19的原根有2,2-4-8-16-13-7-14-9-。。。。
19的原根就一定有4, 4-16-7-9-。。。。。
有8,16所以也就是说如果一个数的原根没有k也就不存在k的幂。
性质二:
记δ = Ordm(a),则a1,……a(δ-1)模 m 两两不同余。因此当a是模m的原根时,a0a1,……a(δ-1)构成模 m 的简化剩余系。
性质三:
模m有原根的充要条件是
m = 1 , 2 , 4 , p , 2 ∗ p , p n , 2 ∗ p n 其 中 p 是 奇 质 数 , n 是 任 意 正 整 数 。 m= 1,2,4,p,2*p,p^n,2*p^n其中p是奇质数,n是任意正整数。m=1,2,4,p,2∗p,p^n ,2∗p^n
其中p是奇质数,n是任意正整数。
性质四:
对正整数(a,m) = 1,如果 a 是模 m 的原根,那么 a 是整数模n乘法群(即加法群 Z/mZ的可逆元,也就是所有与 m 互素的正整数构成的等价类构成的乘法群)Zn的一个生成元。由于Zn有 φ(m)个元素,而它的生成元的个数就是它的可逆元个数,即 φ(φ(m))个,因此当模m有原根时,它有φ(φ(m))个原根。
模m有原根的充要条件:
m=2 m=4 m=P^a m=2*P^a
将P-1进行质因数分解
枚举i,并判断对于每个i是否都有(可以应用快速幂)
第一个符合条件的i就是P的最小原根
对 于 合 数 , 只 要 将 2. 中 的 p − 1 替 换 成 φ ( p ) 即 可 . 对于合数,只要将 2. 中的p-1替换成φ(p)即可.对于合数,只要将2.中的p−1替换成φ(p)即可.
#include<cstdio>
#include<cmath>
inline int phi(int n)
{
int zc=n,all=sqrt(n);
for(int i=2;i<=all;i++)
{
if(n%i!=0)continue;
zc=zc/i*(i-1);
while(n%i==0)n/=i;
}
if(n>1)zc=zc/n*(n-1);
return zc;
}
inline int pow(int x,const int y,const int mod)
{
int res=1;
for(int i=1;i<=y;i<<=1,x=x*x%mod)if(i&y)res=res*x%mod;
return res;
}
inline int G(const int m)
{
const int PHI=phi(m);
for(int g=2;;g++)
{
bool fla=1;
if(pow(g,PHI,m)!=1)continue;
for(int i=1;i<PHI;i++)
if(pow(g,i,m)==1)
{
fla=0;
break;
}
if(fla)return g;
}
}
int m,g;
int main()
{
scanf("%d",&m);
g=G(m);
printf("%d",g);
return 0;
}
在上面的代码中,容易发现,枚举的i并不是每个每个都有用的, 由性质1可得 枚举i只需要枚举φ(m)的因数就好了
#include<cstdio>
#include<cmath>
inline int phi(int n)
{
int zc=n,all=sqrt(n);
for(int i=2;i<=all;i++)
{
if(n%i!=0)continue;
zc=zc/i*(i-1);
while(n%i==0)n/=i;
}
if(n>1)zc=zc/n*(n-1);
return zc;
}
inline int pow(int x,const int y,const int mod)
{
int res=1;
for(int i=1;i<=y;i<<=1,x=(long long)x*x%mod)if(i&y)res=(long long)res*x%mod;
return res;
}
int q[200001];
inline int G(const int m)
{
const int PHI=phi(m);
q[0]=0;
for(int i=2;i<PHI;i++)if(PHI%i==0)q[++q[0]]=i;
for(int g=2;;g++)
{
bool fla=1;
if(pow(g,PHI,m)!=1)continue;
for(int i=1;i<=q[0];i++)
if(pow(g,q[i],m)==1)
{
fla=0;
break;
}
if(fla)return g;
}
}
int m,g;
int main()
{
scanf("%d",&m);
g=G(m);
printf("%d",g);
return 0;
}
最快的代码:
#include<cstdio>
#include<cmath>
inline int phi(int n)
{
int zc=n,all=sqrt(n);
for(int i=2;i<=all;i++)
{
if(n%i!=0)continue;
zc=zc/i*(i-1);
while(n%i==0)n/=i;
}
if(n>1)zc=zc/n*(n-1);
return zc;
}
inline int pow(int x,const int y,const int mod)
{
int res=1;
for(int i=1;i<=y;i<<=1,x=(long long)x*x%mod)if(i&y)res=(long long)res*x%mod;
return res;
}
int q[100001];
inline int G(const int m)
{
const int PHI=phi(m);
q[0]=0;
const int limit=sqrt(PHI);int zc=PHI;
for(int i=2;i<=limit;i++)
if(zc%i==0)
{
q[++q[0]]=PHI/i;
while(zc%i==0)zc/=i;
}
if(zc>1)zc=q[++q[0]]=PHI/zc;
for(int g=2;;g++)
{
bool fla=1;
if(pow(g,PHI,m)!=1)continue;
for(int i=1;i<=q[0];i++)
if(pow(g,q[i],m)==1)
{
fla=0;
break;
}
if(fla)return g;
}
}
int m,g;
int main()
{
scanf("%d",&m);
g=G(m);
printf("%d",g);
return 0;
}