原根

原根的简要学习，为 NTT 做准备

# 阶的概念

要学习原根，就要先引出阶的概念。

根据欧拉定理，我们有：若 $gcd(a,m)=1$ ，则 $a^{\varphi(m)} \equiv 1 \pmod {m}$ 。所以一定存在一个最小正整数 $x$ ，满足 $a^x \equiv 1 \pmod {m}$ ，这个 $x$ 就叫做 $a$ 模 $m$ 的阶，记为 $\delta _m(a)$ 。

# 阶的性质

性质 1： $a,a^2,a^3,\cdots ,a^{\delta _m(a)}$ 模 $m$ 两两不同余。

​ 假设存在 $a^i \equiv a^j \pmod {m}$ ，则 $a^{i-j} \equiv 1 \pmod {m}$ ，与阶的最小正整数这一性质矛盾。

性质 2： 若 $a^x \equiv 1 \pmod {m}$ ， 则 $\delta_m(a) |x$ 。

​ 显然成立。

性质 3： 若 $gcd(a,m)=1$ ，则 $\delta _m(a^k) = \frac{\delta_m(a)}{gcd(\delta_m(a),k)}$ 。

​ $a^{k \cdot \delta_m(a^k)} \equiv a^{\delta_m(a)} \pmod{m}$ ，$\delta _m(a) | k\cdot \delta_m(a^k)$ ，则 $\frac{\delta_m(a)}{gcd(\delta_m(a),k)} | \delta_m(a^k)$ 。

​ $(a^k)^{\frac{\delta_m(a)}{gcd(\delta_m(a),k)}} = (a^{\delta_m(a)})^{\frac{k}{gcd(\delta_m(a),k)}} \equiv 1 \pmod{m}$ ，则 $\delta_m(a^k) | \frac{\delta_m(a)}{gcd(\delta_m(a),k)}$ 。

​ 所以 $\delta _m(a^k) = \frac{\delta_m(a)}{gcd(\delta_m(a),k)}$ 。

这条性质在下面的原根计算中有用处。

# 原根的概念

若 $gcd(a,m)=1$ ，且 $\delta_m(a)=\varphi(m)$ ，则 $a$ 为模 $m$ 的原根。

# 与原根有关的一些定理

原根判断定理： 若 $m\ge 3， gcd(a,m)=1$ ，则 $a$ 为模 $m$ 的原根的充要条件是：对于 $\varphi(m)$ 的每个质因子 $p$ ，都有 $a^{\frac{\varphi(m)}{p}} \not\equiv 1 \pmod{m}$ 。

原根个数定理： 若 $m$ 有原根 $g$ ，则 $m$ 的原根个数为 $\varphi(\varphi(m))$ 。

​ 由阶的性质 3 可得，$\delta_m(g^k) = \frac{\delta_m(g)}{gcd(\delta_m(g),k)} = \frac{\varphi(m)}{gcd(\varphi(m),k)}$ 。则当 $gcd(\varphi(m),k)=1$ 时，$\delta_m(g^k)=\delta_m(g)$ ，即 $g^k$ 也是 $m$ 的原根。易知 $1\le k\le \varphi(m)$ 中这样的 $k$ 有 $\varphi(\varphi(m))$ 个 ，则原根的个数也是这么多。

原根存在定理： 对于一个数 $m$ ，其存在原根当且仅当 $m=2,4,p^k,2p^k$ ，其中 $p$ 为奇质数，$k$ 为正整数。

最小原根定理： 若 $m$ 有原根，则其最小原根小于等于 $m^{0.25}$ 。

有了这四个基本定理，我们就可以求一个数的原根了。

# luogu P6091【模板】原根

​ 给定整数 $n$ ，求它的所有原根。$n\le10^6$

一：我们先线性筛，求出质数以及欧拉函数值。

二：我们标记所有有原根的数。具体来说，根据原根存在定理，枚举所有奇质数，将其正整数幂以及正整数幂乘 $2$ 以后的值标记为有原根，别忘了特判 $2$ 和 $4$ 。

三：我们将 $\varphi(n)$ 分解质因数，同时标记其质因数的所有倍数，被标记的数满足其与 $\varphi(n)$ 的 $gcd$ 不为 $1$ 。

四：我们暴力枚举其最小原根。根据最小原根定理，其复杂度是可以接受的。假设我们枚举到了 $x$ ，先判断 $x^{\varphi(m)} \equiv 1 \pmod{n}$ 是否成立。若不成立一定不是原根，若成立，再根据原根判断定理，我们依次枚举 $\varphi(n)$ 的质因子 $p$ ，判断 $x^{\frac{\varphi(m)}{p}} \equiv 1 \pmod{n}$ 是否成立。若对于所有质因子都成立，则我们找到了 $n$ 的最小原根 $x$ 。

五：我们要根据最小原根 $g$ 找出所有原根。根据原根个数定理，我们暴力从 $1$ 到 $\varphi(n)$ 枚举 $k$ ，可以直接判断其与 $\varphi(n)$ 的 $gcd$ 是否为 $1$ ，但我们有复杂度更优秀的做法。利用三中标记的数，如果 $k$ 没被标记，那么它与 $\varphi(n)$ 的 $gcd$ 一定为 $1$ ，此时我们就又找到了一个原根 $g^k$ 。最后我们就得到了$n$ 的所有原根。

代码如下

#include <iostream>

#include <algorithm>

using namespace std;

const int N=1e6+9;

typedef long long int ll;

int T,P[11][2],maxx,pri[N],cnt,phi[N],p[N],ans[N];

bool st[N],vis[N],f[N];

inline int read()

{

	int x=0,f=1;char c=getchar();

	while(c<'0' || c>'9') {if(c=='-') f=-1;c=getchar();}

	while(c>='0' && c<='9') {x=x*10+c-48,c=getchar();}

	return x*f;

}

inline int quick_pow(int x,int y,int mod)

{

	int ans=1;

	while(y!=0)

	{

		if(y&1) ans=(ll)ans*x%mod;

		x=(ll)x*x%mod;

		y>>=1;

	}

	return ans;

}

int main()

{

	T=read();

	for(int i=1;i<=T;i++)

	{

		P[i][0]=read(),P[i][1]=read();

		maxx=max(maxx,P[i][0]); 

	}

	for(int i=2;i<=maxx;i++)

	{

		if(st[i]==false) pri[++cnt]=i,phi[i]=i-1;

		for(int j=1;j<=cnt;j++)

		{

			if(i>maxx/pri[j]) break;

			st[i*pri[j]]=true;

			if(i%pri[j]==0)

			{

				phi[i*pri[j]]=phi[i]*pri[j];

				break;

			}

			phi[i*pri[j]]=phi[i]*phi[pri[j]];

		}

	}

	f[2]=f[4]=true;

	for(int i=2;i<=cnt;i++)

	{

		int p=pri[i];

		for(int j=1;(ll)j*p<=maxx;j*=p) f[j*p]=true;

		for(int j=2;(ll)j*p<=maxx;j*=p) f[j*p]=true;

	}

	for(int t=1;t<=T;t++)

	{

		int mod=P[t][0],d=P[t][1];

		if(f[mod]==false)

		{

			printf("0\n\n");

			continue;

		}

		int x=phi[mod],sum=0,g=0,tot=0;

		for(int i=1;i<=cnt && pri[i]<=x/pri[i];i++)

		{

			if(x%pri[i]==0)

			{

				while(x%pri[i]==0) x/=pri[i];

				p[++sum]=pri[i];

				for(int j=1;j<=phi[mod]/pri[i];j++) vis[j*pri[i]]=true;

			}

		}

		if(x>1)

		{

			p[++sum]=x;

			for(int j=1;j<=phi[mod]/x;j++) vis[j*x]=true;

		}

		for(int i=1;i<mod;i++)

		{

			while(quick_pow(i,phi[mod],mod)!=1) i++;

			bool flag=true;

			for(int j=1;j<=sum && flag==true;j++)

				if(quick_pow(i,phi[mod]/p[j],mod)==1) flag=false;

			if(flag==true)

			{

				g=i;

				break;

			}

		}

		for(int i=1,x=g;i<=phi[mod];i++,x=(ll)x*g%mod)

		{

			if(vis[i]==false) ans[++tot]=x;

			else vis[i]=false;

		}

		sort(ans+1,ans+tot+1);

		printf("%d\n",tot);

		for(int i=1;i<=tot/d;i++) printf("%d ",ans[i*d]);

		puts("");

	}

	return 0;

}

我们来计算一下其时间复杂度。第一步 $O(n)$ ，第二步 $O(n)$ ，第三步中分解质因数 $O(\sqrt{n} \,\log n)$ ，第四步 $O(n^{0.25}\log n\log\log n)$ ，第五步标记倍数类似于埃氏筛的操作 $O(n\log\log\log n)$ 。最后排序可以用计数排序做到 $O(n)$ ，最终时间复杂度为 $O(n\log\log\log n)$ ，由于 $\log\log\log n$ 约为常数，所以时间复杂度近似认为是 $O(n)$ 。

# 总结

原根的作用还是不小的，可以用于离散对数。在 OI 中最主要的就是在 NTT 中使用了。可以记一些常见模数的原根，如 $998244353$ 的原根是 $3$ ，$10^9+7$ 的原根是 $5$ 。