文章目录

• 原根
• BSGS大步小步算法
• 扩展BSGS

原根

如果两个整数$a,b$互质，则有$a^{\varphi (b)}\%b=1$

定义模$b$意义下的$a$的阶为使$a^d\%b=1$的最小正整数$d$

显然，模$b$的阶$d|\varphi (b)$

如果模$b$意义下$a$的阶为$\varphi (b)$，则称$a$为$b$的原根

欧拉证明了（我证明不了）

模$b$存在原根的充要条件为：$b=2,4,p^n,2p^n$，其中$p$为奇素数，$n\in N^{\ast }$

当模$b$有原根时，其原根个数为$\varphi (\varphi (b))$

那么如何求一个数的原根？

首先判断它是否有原根

如果有，一般最小原根都很小，可以选择美丽的暴力

预处理出$\varphi (b)$的所有因子，存放在数组$D$中

在$[2,\varphi (b))$区间中，从小到大米枚举变量$i$

如果存在$j\in D$，使得$i^{\frac{\varphi (b)}{j}}\%b=1$，则$i$不是原根，否则$i$是原根

为什么这样是正确的呢？

因为如果存在一个数$1\le x<\varphi (b)$，使得$i^x\%b=1$

则$x|\varphi (b)$，并且一定存在一个$\varphi (b)$的质因子$j$，使得$x|\frac{\varphi (b)}{j}$

---

BSGS大步小步算法

BSGS是用来解决离散对数问题的

即$a^x\equiv b(modp)$，其中$a,b,p$已知，且$(a,p)=1$，求$x$

因为$a^{\varphi (p)}\equiv 1(modp),\varphi (p)<p$

所以可以采取枚举法，在$O(p)$的时间复杂度求出$x$

而$BSGS$可以在$O(\sqrt{p})$的时间复杂度内求出$x$

令$m=\lceil \sqrt{p}\rceil ,r=x\mathrm{m}\mathrm{o}\mathrm{d}m$，则$x=k\ast m+r$，其中$0\le k<m,0\le r<k$，有
$$a^{k\ast m+r}\equiv b(modp)$$

因为$(a,p)=1$，方程两边同乘$a^{-r}$

$$a^{k\ast m}\equiv b\ast a^{-r}(modp)$$

对于$0\le i<r$，求出所有的$b\ast a^{-1}\mathrm{m}\mathrm{o}\mathrm{d}p$，将其值以及$i$存入$map$

然后再求左边的$a^{j\ast m}\mathrm{m}\mathrm{o}\mathrm{d}p,(0\le j<k)$，并在$map$里寻找是否出现过相同的值

如果有，代表着同余，已经找到了答案，如果没有则是无解

然而。。。

可以稍微转变一下算法过程，避免求逆元的操作

$$x=k\ast m+r=(k+1)\ast m-m+r=(k+1)\ast m-(m-r)$$
因为有 $r<m$ 所以考虑换一种方式枚举 $r\leftarrow m-r$
$$\Rightarrow x=k\ast m-r，(1\le k\le m,0\le r<m)$$
则$$a^{k\ast m-r}\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}p)$$
两边同时乘以$a^r$
$$a^{k\ast m}\equiv b\ast a^r(\mathrm{m}\mathrm{o}\mathrm{d}p)$$
先求出右边所有的$b\ast a^i(\mathrm{m}\mathrm{o}\mathrm{d}p)(1\le i\le m)$保存在$map$中

然后再求左边的$a^{j\ast m}\mathrm{m}\mathrm{o}\mathrm{d}p$，并在$map$中查找是否出现过

如果出现过，左边枚举的是$j$，右边枚举的是$i$，则答案为$x=j\ast m-i$，这样就避免了求逆元的操作，却仍然用到了逆元

因为推导必须是等价推导，只有当$(a,p)=1$，即$a^r$逆元存在时，才可以大胆两边同乘$a^r$等价，因为如果$(a,p)\ne 1$，式子倒推不回去

#include <map> #include <cmath> #include <cstdio> using namespace std; #define int long long map < int, int > mp; int a, mod, r;int bsgs() {mp.clear();int m = ceil( sqrt( mod ) );int tmp = 1;for( int i = 1;i <= m;i ++ ) {tmp = tmp * a % mod;mp[tmp * r % mod] = i;}int res = 1;for( int i = 1;i <= m;i ++ ) {res = res * tmp % mod;if( mp[res] ) return m * i - mp[res];}return -1; }signed main() {int ans;while( ~ scanf( "%lld %lld %lld", &mod, &a, &r ) ) {r %= mod, a %= mod;if( r == 1 ) ans = 0;else if( ! a ) {if( r ) ans = -1;else ans = 1;}else ans = bsgs();if( ans == -1 ) printf( "no solution\n" );else printf( "%lld\n", ans );}return 0; }

---

扩展BSGS

对于$a^x\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}p)$

如果$(a,p)>1$，则无法直接套用BSGS，此时就要用到扩展BSGS

将要求解的式子变形
$$a^x+k\ast p=b$$
设$(a,p)=g$，若$b$不是$g$的倍数，则方程无解

不过有一个例外$b=1,x=0$，这个情况特判即可

式子左右两边除以$g$
$$a^{x-1}\frac{a}{g}+k\frac{p}{g}=\frac{b}{g}$$
令$a^{\prime }=\frac{a}{g},p^{\prime }=\frac{p}{g},b^{\prime }=\frac{b}{g}$
$$a^{x-1}{a}^{\prime }+k{p}^{\prime }=b^{\prime }$$
若$a,p^{\prime }$仍然不互质，则继续以上操作找出$a,p^{\prime }$的最大公约数$g^{\prime }$

最新式子两边继续除以$g^{\prime }$，直到$(a,p^{\prime })=1$为止

在此过程中，假设取出来了$cnt$个$a$，出去公约数后剩下的乘积为$a^{\prime }$

此时$(a^{\prime },p^{\prime })=1$，于是可以转化为$$a^{x-cnt}{a}^{\prime }\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}p)\iff a^{x-cnt}\equiv b^{\prime }(a^{\prime }{)}^{-1}(\mathrm{m}\mathrm{o}\mathrm{d}p)$$
其中$cnt$表示两边除以最大公约数$g$的次数

此处右边有逆元，为了避免求逆元，将$a^{\prime }$保留在左边

在BSGS枚举左边时，初始值设为$a^{\prime }$即可

如果在除以$g$的过程中，发现$b^{\prime }(a^{\prime }{)}^{-1}=1\iff b^{\prime }\equiv a^{\prime }\Rightarrow x-cnt=0\Rightarrow x=cnt$

接下来，直接套用基础BSGS即可，记得最后的答案不要忘记加上$cnt$哟(＾Ｕ＾)ノ~ＹＯ

#include <map> #include <cmath> #include <cstdio> using namespace std; #define int long long map < int, int > mp; int a, mod, r;int gcd( int x, int y ) {if( ! y ) return x;else return gcd( y, x % y ); }int qkpow( int x, int y, int mod ) {int ans = 1;while( y ) {if( y & 1 ) ans = ans * x % mod;x = x * x % mod;y >>= 1;}return ans; }int exbsgs() {if( r == 1 ) return 0;int cnt = 0, tmp = 1, d;while( 1 ) {d = gcd( a, mod );if( d == 1 ) break;if( r % d ) return -1;r /= d, mod /= d;tmp = tmp * ( a / d ) % mod;++ cnt;if( tmp == r ) return cnt;}mp.clear();int res = r;mp[r] = 0;int m = ceil( sqrt( 1.0 * mod ) );for( int i = 1;i <= m;i ++ ) {res = res * a % mod;mp[res] = i;}int temp = qkpow( a, m, mod );res = tmp;for( int i = 1;i <= m;i ++ ) {res = res * temp % mod;if( mp.count( res ) )return i * m - mp[res] + cnt;}return -1; }signed main() {while( ~ scanf( "%lld %lld %lld", &a, &mod, &r ) ) {if( ! a && ! mod && ! r ) return 0;int ans = exbsgs();if( ans == -1 ) printf( "No Solution\n" );else printf( "%lld\n", ans );}return 0; }

---

总结

以上是生活随笔为你收集整理的【学习笔记】原根 / BSGS / 扩展BSGS证明及模板的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。