This is not the end.

0%

原根 primitive root

Posted on

定义

对于某一个g∈[0,p)，如果对于{0,1,⋯p−1}中每一个与p互质的数x，都存在一个k使得gk≡xmodp，那么就称g是p的一个原根。也就是说，g0,g1,⋯gφ(n)−1在模n的意义下两两不同。

检测一个数是否为p的原根

现在还没有快速的计算一个数的原根的算法。但是，我们有一种比较快的检测一个数是否为p的原根的方法。

阶 multiplicative order

在模p的意义下，定义某个满足gcd(a,p)=1的a的阶为，满足ak≡1modp的最小正整数k，记为δp(a)。

阶有一些性质：
1）如果aN≡1modp，那么N一定是a的阶的倍数。并且，根据欧拉定理，N一定是φ(p)的因数。
2）原根的阶等于φ(p)。

容易推出，对于一个x，如果它不是p的原根，那么他的阶一定小于φ(p)并且是φ(p)的因数。我们只需要对于φ(p)的每一个因数d，判断xd≡1modp是否成立就好了。实际上，由于阶的性质，我们处理出φ(p)的所有质因子pr1,pr2⋯prk，然后判断xφ(p)pri≡1modp是否成立，就可以判断x是不是原根。因为如果x的阶小于φ(p)，那么φ(p)pri中，至少有一个是δp(x)的倍数。

这个检测的复杂度应该是O(plog⁡p)的。

求最小原根

求最小原根的算法：从2开始依次枚举，依次检验每一个枚举到的数，当检验出一个数为原根的时候就退出。这个算法的复杂度是与最小原根的大小相关的。呃，一个数最小原根的大小大概也许一般是比较小的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define ll long long
using namespace std;
template <class T>
inline void read(T &x)
{
	x=0; char c=getchar(); int f=1;
	while(!isdigit(c)){if(c=='-')f=-1; c=getchar();}
	while(isdigit(c)) x=x*10-'0'+c,c=getchar(); x*=f;
}
const int N=32010;
int pri[N],num,flg[N];
int gcd(int a,int b){return b?gcd(b,a%b):a;}
void predo(int n){for(int i=2;i<=n;++i){if(!flg[i])pri[num++]=i; for(int j=0;j<num&&pri[j]*i<=n;++j){flg[i*pri[j]]=1; if(i%pri[j]==0) break;}}}
int d[N],tot,mod;
int Pow(int x,int y){int res=1;while(y){if(y&1) res=res*(ll)x%mod; x=x*(ll)x%mod,y>>=1;}return res;}
void get(int p){tot=0; for(int j=0;j<num&&pri[j]*pri[j]<=p;++j){if(p%pri[j]==0){d[++tot]=pri[j]; while(p%pri[j]==0) p/=pri[j]; }} if(p>1) d[++tot]=p; }
bool che(int x){if(gcd(x,mod)!=1) return 0;for(int i=1;i<=tot;++i) if(Pow(x,(mod-1)/d[i])==1) return 0; return 1;}
int main()
{
	predo(N-10); read(mod),get(mod-1);
	for(int i=2;i<mod;++i)
	if(che(i)){printf("%d",i); break;}
	return 0;
}

原根数量&&求一个数所有的原根

对于一个p，如果它的原根存在，那么它的原根的数量是φ(φ(p))。

假设g是p的原根，并且gcd(i,φ(p))=1，那么gi也是p的一个原根。原因是当gcd(i,φ(p))=1，i的k倍可以遍历φ(p)的剩余集，也就是说，gi的幂次可以取遍[0,p)中，所有与p互质的数。

因此，对于一个数p，如果它的原根存在，那么一定有φ(φ(p))个。

由此，我们可以得到求一个数所有的原根的算法：先求出最小原根，然后取所有与φ(p)互质的i，就可以得到所有的原根了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#define PB push_back
#define ll long long
using namespace std;
template <class T>
inline void read(T &x)
{
	x=0; char c=getchar(); int f=1;
	while(!isdigit(c)){if(c=='-')f=-1; c=getchar();}
	while(isdigit(c)) x=x*10-'0'+c,c=getchar(); x*=f;
}
const int N=1000010;
int pri[N],num,flg[N],phi[N];
int gcd(int a,int b){return b?gcd(b,a%b):a;}
void predo(int n)
{
	for(int i=2;i<=n;++i)
	{
		if(!flg[i])pri[num++]=i,phi[i]=i-1;
		for(int j=0;j<num&&pri[j]*i<=n;++j)
		{
			flg[i*pri[j]]=1;
			if(i%pri[j]==0) {phi[i*pri[j]]=phi[i]*pri[j]; break;}
			else phi[i*pri[j]]=phi[i]*phi[pri[j]];
		}
	}
}
int d[N],tot,mod;
int Pow(int x,int y){int res=1;while(y){if(y&1) res=res*(ll)x%mod; x=x*(ll)x%mod,y>>=1;}return res;}
void get(int p){tot=0; for(int j=0;j<num&&pri[j]*pri[j]<=p;++j){if(p%pri[j]==0){d[++tot]=pri[j]; while(p%pri[j]==0) p/=pri[j]; }} if(p>1) d[++tot]=p; }
bool che(int x){if(gcd(x,mod)!=1) return 0;for(int i=1;i<=tot;++i) if(Pow(x,phi[mod]/d[i])==1) return 0; return 1;}
int Get(){get(phi[mod]);for(int i=2;i<mod;++i) if(che(i)) return i;}
bool check(int p)
{
	if(p==2||p==4) return 1; if(p%2==0) p/=2; if(p%2==0) return 0;
	for(int j=1;pri[j]*pri[j]<=p&&j<num;++j) if(p%pri[j]==0){while(p%pri[j]==0) p/=pri[j]; return p==1;}
	return 1;
}
vector<int> ans;
void solve()
{
	if(!check(mod)){ puts("-1"); return;}
	if(mod==2) {puts("1"); return;}
	int g=Get(),k=g; ans.clear();
	for(int i=1;i<phi[mod];++i){if(gcd(i,phi[mod])==1) ans.PB(k); k=k*(ll)g%mod;}
	sort(ans.begin(),ans.end());
	for(int i=0;i<ans.size();++i) printf("%d%c",ans[i],i==ans.size()-1?'\n':' ');
}
int main()
{
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	predo(N-10);
	while(~scanf("%d",&mod)) solve();
	return 0;
}

原根存在的条件

丢一个结论在这里：一个数m存在原根，当且仅当m=2,4,pa,2×pa，其中p为奇质数，a为正整数。

所以把判断一个数是否有原根的函数放在这里。代码中，pri数组下标从0开始，pri[0]=2,pri[1]=3。

1
2
3
4
5
6
bool check(int p)
{
	if(p==2||p==4) return 1; if(p%2==0) p/=2; if(p%2==0) return 0;
	for(int j=1;pri[j]*pri[j]<=p&&j<num;++j) if(p%pri[j]==0){while(p%pri[j]==0) p/=pri[j]; return p==1;}
	return 1;
}