BSGS-Junior·BSGS算法初探

$\rm{0x01}$ $\mathcal{Preface}$

$\rm{BSGS}(Baby~Step~Giant~Step)$, 大步小步法。当然也会被叫做拔山盖世北上广深算法……咳,这并不重要。形式化地讲, $\rm{BSGS}$算法主要用来解决以下问题 :

给定质数$p$, 整数$a, b$, $(a, p)=1$.求最小的非负整数$x$, 使得$a^x≡ b~(\mod p)$

而首先我们知道的,是由欧拉定理$a ^{\varphi(p)} ≡ 1 ~(\mod p)$,并且我们还知道$a^0=1≡1 ~(\mod p)$,所以我们可以得出一个断言:

如果方程$a^x≡ b~(\mod p)$有最小非负整数解,那么最小非负整数解一定在$[0, \varphi(p))$中 $\qquad \qquad(1) $

此处肉眼可以看出其循环节为$\varphi(p)$,不再证明。

之后我们将以此为基础进行类似分块的操作——

$\rm{0x02~~Baby~Step~Giant~Step}$

首先我们记$n=\sqrt {\varphi(p)}$,那么$\forall x \in [0, \varphi(p))$, $x = i\times m+j$, $i \leq \lfloor \frac{p−1-m}{m} \rfloor,~~ 0≤j <m$ 。那么对于原方程我们可以把其改为:$$a^{i\cdot n+j}≡ b~(\mod p)$$移一下项就可以变成$$a^j ≡b \cdot a^{-i\cdot n} (\mod p)$$那么现在我们的策略是算出所有$a^j$来,在$\mod p$ 意义下观察是否有一个$i$使得$a^j ≡b \cdot a^{-i\cdot n} (\mod p)$。我们称左边枚举$a^j$叫做小步$(\rm{Baby~Step})$, 称右边枚举$b \cdot a^{-i\cdot n}$叫做大步$~(\rm{Giant~Step})$

那么其实算法流程很明晰了,我们只需要循环两次、第一次记录的$a^j$用哈希表($STL$自带$unordered$_ $map$)记录一下即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
inline LL expow(LL a, LL b, LL p){
LL res = 1 ;
while (b){
if (b & 1)
(res *= a) %= p ;
(a *= a) %= p, b >>= 1 ;
}
return res % p ;
}
inline void bsgs(LL x, LL y, LL p){
P = ceil(sqrt(p)), Hash.clear(), Q = expow(x, -P + 2 *(p - 1), p) ;
//a ^ (p-1) = 1 (mod p) => Q = a^(-P) = a ^(-P + p -1) ;
for (LL i = 1, j = 0 ; j < P ; ++ j, (i *= x) %= p)
if (!Hash.count(i)) Hash[i] = j ; // Push them into hash_table
for (LL i = y, j = 0 ; j <= P ; ++ j, (i *= Q) %= p)
if (Hash.count(i)){ cout << Hash[i] + j * P << endl ; return ; }
cout << "-1" << endl ;
}

其中细节还是有的:

  • 计算sqrt时要上取整

  • 我们在求$a^{-i\cdot n}$时用的底变量需要由费马小定理求快速幂得出。但是此时指数上可能为负数,所以我们选择加上一个模数,不影响结果。

  • 两次循环枚举的边界要注意有的是$\leq$有的是$<$
  • 算法还没开始时,要判断本身$a$是否可以被$P$整除。如果不特判这种情况的话,我们上面代码中的Q就会=0,从而在下面的第二个循环处出错——我们的hash[i]j不能同时为$0$,从而输出错误的答案。

$\rm{0x03}$ 例题

$T1~$$LuoguP4028$

裸题,但是有很多坑……或者说上面列举的细节都涵盖了qaq

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
#include <cmath>
#include <cstdio>
#include <iostream>
#include<tr1/unordered_map>

#define LL long long

using namespace std ;
using namespace tr1 ; int T ;
LL A, B, M, P, Q ; unordered_map <LL, LL> Hash ;

inline LL expow(LL a, LL b, LL p){
LL res = 1 ;
while (b){
if (b & 1)
(res *= a) %= p ;
(a *= a) %= p, b >>= 1 ;
}
return res % p ;
}
inline void bsgs(LL x, LL y, LL p){
P = ceil(sqrt(p)), Hash.clear(), Q = expow(x, -P + 2 *(p - 1), p) ;
//a ^ (p-1) = 1 (mod p) => Q = a^(-P) = a ^(-P + p -1) ;
for (LL i = 1, j = 0 ; j < P ; ++ j, (i *= x) %= p)
if (!Hash.count(i)) Hash[i] = j ; // Push them into hash_table
for (LL i = y, j = 0 ; j <= P ; ++ j, (i *= Q) %= p)
if (Hash.count(i)){ cout << Hash[i] + j * P << endl ; return ; }
cout << "Couldn't Produce!" << endl ;
}
inline LL qr(){
LL res = 0 ; char c = getchar() ; while (!isdigit(c)) c = getchar() ;
while (isdigit(c)) res = (res << 1) + (res << 3) + c - 48, c = getchar() ;
return res ;
}
int main(){
cin >> T ;
while (T --){
M = qr(), A = qr(), B = qr() ;
if ((!(A % M == 0 && B))) bsgs(A, B, M) ;
else cout << "Couldn't Produce!" << endl ;
}
return 0 ;
}

$T2~$ $TJOI2007~Cute~Prime$

最裸最裸的、无特判的题……可以水一下双倍经验。

$\mathfrak{writter: pks}$