【学习笔记】BSGS算法初探

一类 $a^x\equiv b\pmod p$,且 $p$ 为素数时的同余式解法。

前言

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

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

由欧拉定理可知 $a ^{\varphi(p)} ≡ 1 \pmod p$,并且还有 $a^0≡1 \pmod p$,所以我们可以得出一个断言:

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

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

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

Baby Step Giant Step

首先我们记 $n=\sqrt {\varphi(p)}$,那么 $\forall x \in [0, \varphi(p)), x = i\times m+j$ 有

那么对于原方程,我们可以把其改为

移一下项就可以变成

那么现在我们的策略是算出所有 $a^j$ 来,在$\bmod p$ 意义下观察是否有一个 $i$ 可以使得

我们称左边枚举 $a^j$ 叫做 小步 (Baby Step)​,称右边枚举 $b \cdot a^{-i\cdot n}$ 叫做 大步(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$ ,从而输出错误的答案。

例题

LG P4028

裸题,但是有很多坑……或者说上面列举的细节都涵盖了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 ;
}

[TJOI2007] CutePrime​

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

总结

这可能是我来培训第一个听的比较懂的算法了,撒花~