文章目錄

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

原根

如果兩個整數$a,b$互質，則有$a^{?(b)}\%b=1$

定義模$b$意義下的$a$的階為使$a^d\%b=1$的最小正整數$d$

顯然，模$b$的階$d|?(b)$

如果模$b$意義下$a$的階為$?(b)$，則稱$a$為$b$的原根

歐拉證明了（我證明不了）

模$b$存在原根的充要條件為：$b=2,4,p^n,2p^n$，其中$p$為奇素數，$n\in N^{?}$

當模$b$有原根時，其原根個數為$?(?(b))$

那么如何求一個數的原根？

首先判斷它是否有原根

如果有，一般最小原根都很小，可以選擇美麗的暴力

預處理出$?(b)$的所有因子，存放在數組$D$中

在$[2,?(b))$區間中，從小到大米枚舉變量$i$

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

為什么這樣是正確的呢？

因為如果存在一個數$1\le x<?(b)$，使得$i^x\%b=1$

則$x|?(b)$，并且一定存在一個$?(b)$的質因子$j$，使得$x|\frac{?(b)}{j}$

---

BSGS大步小步算法

BSGS是用來解決離散對數問題的

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

因為$a^{?(p)}\equiv 1(modp),?(p)<p$

所以可以采取枚舉法，在$O(p)$的時間復雜度求出$x$

而$BSGS$可以在$O(\sqrt{p})$的時間復雜度內求出$x$

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

因為$(a,p)=1$，方程兩邊同乘$a^{?r}$

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

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

然后再求左邊的$a^{j?m}\mathrm{m}\mathrm{o}\mathrm{d}p,(0\le j<k)$，并在$map$里尋找是否出現過相同的值

如果有，代表著同余，已經找到了答案，如果沒有則是無解

然而。。。

可以稍微轉變一下算法過程，避免求逆元的操作

$$x=k?m+r=(k+1)?m?m+r=(k+1)?m?(m?r)$$
因為有 $r<m$ 所以考慮換一種方式枚舉 $r\leftarrow m?r$
$$?x=k?m?r，(1\le k\le m,0\le r<m)$$
則$$a^{k?m?r}\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}p)$$
兩邊同時乘以$a^r$
$$a^{k?m}\equiv b?a^r(\mathrm{m}\mathrm{o}\mathrm{d}p)$$
先求出右邊所有的$b?a^i(\mathrm{m}\mathrm{o}\mathrm{d}p)(1\le i\le m)$保存在$map$中

然后再求左邊的$a^{j?m}\mathrm{m}\mathrm{o}\mathrm{d}p$，并在$map$中查找是否出現過

如果出現過，左邊枚舉的是$j$，右邊枚舉的是$i$，則答案為$x=j?m?i$，這樣就避免了求逆元的操作，卻仍然用到了逆元

因為推導必須是等價推導，只有當$(a,p)=1$，即$a^r$逆元存在時，才可以大膽兩邊同乘$a^r$等價，因為如果$(a,p)=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?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)?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?b^{\prime }\equiv a^{\prime }?x?cnt=0?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证明及模板的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。