原根
阶与原根
回顾之前学过的欧拉定理，如果$(a,m)=1$，则：
$$a^{\phi(m)}\equiv 1\pmod m$$
所以说，如果$(a,m)=1$，则存在一个最小正整数$n$使得$a^n\equiv 1\pmod m$，这个最小正整数$n$称作$a$模$m$的阶，记作$\delta_m(a)$或者$ord_m(a)$。
**原根**：若$(a,m)=1$，且$\delta_m(a)=\phi(m)$，则称$a$为模$m$的一个原根。
阶的性质
1、若$a^n\equiv 1\pmod m$，则$$\delta_m(a)|n$$
显然，不再证明。
2、设$(a,m)=(b,m)=1$，则$\delta_m(ab)=\delta_m(a)\delta_m(b)$的充要条件是$(\delta_m(a),\delta_m(b))=1$。（积性性质）
证明：
必要性证明：
已知：$a^{\delta_m(a)}\equiv 1\pmod m$，$b^{\delta_m(b)}\equiv 1\pmod m$
可知：
$$(ab)^{[\delta_m(a),\delta_m(b)]}\equiv 1\pmod m$$
所以$\delta_m(ab)|[\delta_m(a),\delta_m(b)]$
又因为$\delta_m(ab)=\delta_m(a)\delta_m(b)$
那么$$\delta_m(a)\delta_m(b)|[\delta_m(a),\delta_m(b)]$$
其实这个式子就意味着：$$\delta_m(a)\delta_m(b)\leq [\delta_m(a),\delta_m(b)]$$
也就是说：$$(\delta_m(a),\delta_m(b))=1$$
充分性证明：
已知：
$$(ab)^{\delta_m(ab)}\equiv 1\pmod m$$
所以：
$$
\begin{aligned}
(ab)^{\delta_m(ab)\delta_m(b)}&\equiv ((ab)^{\delta_m(ab)})^{\delta_m(b)}\pmod m\\
&\equiv 1^{\delta_m(b)}\pmod m\\
&\equiv 1\pmod m
\end{aligned}
$$
另一种角度：
$$
\begin{aligned}
(ab)^{\delta_m(ab)\delta_m(b)}&\equiv a^{\delta_m(ab)\delta_m(b)}b^{\delta_m(ab)\delta_m(b)}\pmod m\\
& \equiv a^{\delta_m(ab)\delta_m(b)} (b^{\delta_m(b)})^{\delta_m(ab)} \pmod m\\
&\equiv a^{\delta_m(ab)\delta_m(b)}\pmod m
\end{aligned}
$$
根据性质一可得：
$$\delta_m(a)|\delta_m(ab)\delta_m(b)$$
又因为$(\delta_m(a),\delta_m(b))=1$，所以：
$$\delta_m(a)|\delta_m(ab)$$
同理，也能得到：
$$\delta_m(b)|\delta_m(ab)$$
又因为$(\delta_m(a),\delta_m(b))=1$，所以：
$$\delta_m(a)\delta_m(b)|\delta_m(ab)$$
所以：
$$\delta_m(ab)=\delta_m(a)\delta_m(b)$$
3、若$(a,m)=1$，则
$$\delta_m(a^k)=\frac{\delta_m(a)}{(\delta_m(a),k)}$$
证明：
$$
\begin{aligned}
(a^k)^{\delta_m(a^k)}&\equiv 1\pmod m\\
&\equiv a^{k\delta_m(a^k)}\pmod m\\
\end{aligned}
$$
所以可知$\delta_m(a)|k\delta_m(a^k)$，所以：
$$\frac{\delta_m(a)}{(\delta_m(a),k)}|\frac{k}{(\delta_m(a),k)}\delta_m(a^k)$$
显然$(\frac{\delta_m(a)}{(\delta_m(a),k)},\frac{k}{(\delta_m(a),k)})=1$，所以：
$$\frac{\delta_m(a)}{(\delta_m(a),k)}|\delta_m(a^k)$$
可知：
$$
\begin{aligned}
(a^{\delta_m(a)})^{\frac{k}{(\delta_m(a),k)}}&\equiv 1\pmod m \\
&\equiv (a^k)^{\frac{\delta_m(a)}{(\delta_m(a),k)}}\pmod m\\
\end{aligned}
$$
所以：
$$\delta_m(a^k)|\frac{\delta_m(a)}{(\delta_m(a),k)}$$
我们已知：$\frac{\delta_m(a)}{(\delta_m(a),k)}|\delta_m(a^k)$以及$\delta_m(a^k)|\frac{\delta_m(a)}{(\delta_m(a),k)}$，所以：
$$\delta_m(a^k)=\frac{\delta_m(a)}{(\delta_m(a),k)}$$
4、$(a,m)=1$，则$a^1,a^2,\cdots ,a^{\delta_m(a)}$模$m$互不相同余。
证明：
设$a^i\equiv a^j\pmod m$，则$a^{i-j}\equiv 1\pmod m$，所以$i-j$是$\delta_m(a)$的倍数，所以$i\equiv j\pmod {\delta_m(a)}$，所以$a^i,a^2,\cdots ,a^{\delta_m(a)}$模$m$互不相同余。
根据这条性质，我们发现，原根其实就是模$m$的既约剩余系的生成元（生成$p-1$个互不相同余的数）。
原根判定定理
**若$(a,m)=1$，则$a$是模$m$的原根的充要条件是$a^{\frac{\phi(m)}{p_i}}\not\equiv 1\pmod m$，其中$p_i$是$m$的所有不同质因子。**
证明：
必要性证明：
设$a$是模$m$的原根，则$a^{\phi(m)}\equiv 1\pmod m$，所以$a^{\frac{\phi(m)}{p_i}}\not\equiv 1\pmod m$。
充分性证明：
设$a^{\frac{\phi(m)}{p_i}}\equiv 1\pmod m$，则$a^{\phi(m)}\equiv (a^{\frac{\phi(m)}{p_i}})^{p_i}\equiv 1\pmod m$，与$a$是模$m$的原根矛盾。
原根的存在定理
一个数字$m$有原根，当且仅当：
1、$m=2$或者$m=4$
2、$m=p^k$，$p$是奇素数，$k\geq 1$
3、$m=2p^k$，$p$是奇素数，$k\geq 1$
在此不再证明。
离散对数（BSGS）
我们知道，如果$a$是模$m$的原根，那么$a^1,a^2,\cdots ,a^{\delta_m(a)}$模$m$互不相同余。
所以，如果$a^x\equiv b\pmod m$，那么$x$一定在$[1,\delta_m(a)]$这个区间内。
$x$的解就可以类比为实数域上的对数，也就是$x=log_a b$。所以，我们称$x$为$b$以$a$为底，模$m$的离散对数。
求解离散对数我们通常使用$BSGS$算法。
$BSGS$算法的思路是：把$x$拆分成$i*m-j$，同余方程变成$(a^m)^i=b*a^j\pmod p$，其中$i\in[1,m]$，$j\in [0,m-1]$，枚举$b*a^j$，然后枚举$(a^m)^i$，找到相同的数，就可以得到$x$。
// 求最小x，使 a^x==b (mod p) ，也就是离散对数log_a b
ll BSGS(ll a,ll b,ll p){
a%=p,b%=p;
if(b==1) return 0; // 特判，x=0的情况
ll m=ceil(sqrt(p));
//把x拆成i*m-j,同余方程变成(a^m)^i=b*a^j(mod p)
//i\in[1,m],j\in [0,m-1]，枚举
unordered_map<int,int> hash;// 记录<b*a^j,j>
ll t=b;
hash[t]=0; // j=0
for(int j=1;j<m;++j){//统计j的不同取值
t=t*a%p;
hash[t]=j;
}
ll am=qpow(a,m,p);
t=1;
for(int i=1;i<=m;++i){//枚举(a^m)^i的不同取值
t=t*am%p;
if(hash.find(t)!=hash.end()) return i*m-hash[t];
}
return -1;//不存在解
}
发表评论