BSGS 算法

缘起

BSGS算法（拔山盖世是否或者北上广深算法）的全名是大小步算法（Baby Step Giant Step）目的是求满足如下同余方程中的t.
$$
x^t ≡ y(mod m)
$$

分析

其思想是费马小定理

如果x和m互质的话，则
$$
x^{m-1} ≡ 1 (mod m)
$$
所以令 k = ceil(sqrt(m))的话（则k^2>=m），令t = k*i-j, 其中 1<=i<=k, 而0<=j<=k, 则带求的同余方程等价于

x^(ik) ≡ x^(j)*y (mod m) ··················································（&&）

所以只需要预处理一下x^(j)*y 模掉m的余数，缓存起来，然后遍历i(从1到k), 只要满足（&&）

则 i*k-j 就是t的一个解.

BSGS算法的复杂度显然是O(sqrt(N))——一款性能还不错的算法

思想好说，下面找道题目来练手

P4454 [CQOI2018]破解D-H协议

样例输入

1
2
3
4
5
3 31
3
27 16
21 3
9 26

样例输出

1
2
3
4
21
25

题意很明确——(g,P,A,B)是公开的（其实确切说g，P是DH协议公开的，而A和B是可观（qie）测（ting）的），所以我们只需要求出a或者b中的一个, 例如

根据

g^a ≡ A(mod P) 求出a来，则马上就可以计算B^a mod P ，K就找到了. 后者是平凡的（快速幂，如果不清楚的话，可以看【2】，这是一款快速幂的板子），前者就是本文介绍的BSGS算法. 

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include "stdafx.h"
#include <iostream>
#include <cstdio>
#include <map>
#include <cmath>
using namespace std;
#define LOCAL

typedef long long LL;

LL g,P,k,r;
map<LL,LL> s,t;
typedef map<LL,LL>::iterator mit;

void bsgs() // 预处理
{
	for (LL i = 0,x=1; i<=k; i++)
	{
		t[r=x%P] = i;
		x = x*g %P;
	} // 最后 r就是 g^k mod P的余数 t[1,...,g^k mod P的余数] = i
	for (LL i = 1, y = r; i<=k; i++)
	{
		s[y%P] = i;
		y = y*r %P;
	} // 最后 s[r,...,r^k mod P 的余数] = i, 即 s[g^k,...,g^(k^2) mod P 的余数] = i;
}

LL qsm(LL B, LL a) // 求B^a mod P 的快速幂（不用快速幂必然吃T） 这里用的是快速幂的标准板子
{
	LL ans = 1;
	while(a)
	{
		if (a&1) // B是奇数
		{
			ans = ans * B %P;
		}
		if (a>1)
		{
			B = B*B %P;
		}
		a = a >>1;
	}
	return ans;
}

LL decypher(LL A, LL B) // g^a≡A(mod P) ,如果 a=k*i-j的话，则g^(ki)≡A*g^j(mod P),而缓存g^(ki)和 g^j mod P 的余数就是预处理方法bsgs()干的事情. 这里只需要乘以A进行验证就行了
{
	mit it = t.begin();
	while(it!=t.end())
	{	
		LL tmp = A*it->first%P; // A*g^j模掉P的余数
		if (s.count(tmp))
		{
			return qsm(B, s[tmp]*k-it->second); // 则返回 a=k*i-j
		}
		it++;
	}
}


int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	LL n;
	scanf("%lld%lld%lld", &g, &P, &n);
	k = ceil(sqrt((double)P));
	bsgs(); // 预处理
	while(n--)
	{
		LL A,B;
		scanf("%lld%lld", &A, &B);
		printf("%lld\n",decypher(A,B));
	}
	return 0;
}

ac情况

评测状态

Accepted

100

用时: 1589ms / 内存: 5008KB

参考

【1】https://blog.csdn.net/chenxiaoran666/article/details/83450304

【2】https://yfsyfs.github.io/2019/07/02/%E5%BF%AB%E9%80%9F%E5%B9%82%E6%A8%A1%E6%9D%BF/