离散对数（BSGS）

离散对数问题，即已知 \(a,b,p\)，求方程 \(a^x \equiv b \pmod p\) 最小非负整数解。

BSGS 算法

原理

思考暴力做法，即枚举 \(x\) 直到满足方程，复杂度 \(\operatorname{O}(p)\)

BSGS 类似一种分块思想，也有点像折半搜索（

首先把 \(x\) 拆开，拆成 \(km - r\) ，然后进行变换： \[ \begin{aligned} a^x &\equiv b \pmod p \newline a^{km-r} &\equiv b \pmod p \newline \frac {a^{km}}{a^r} & \equiv b \pmod p \newline a^{km} & \equiv ba^r \pmod p \end{aligned} \] 这里的 \(m\) 我们设为一个固定值，然后分别枚举等式两边的 \(k,r\)，存哈希表（映射），然后匹配即可，其中 \(k \in [0, \cfrac pm], r \in [0,m]\) ，复杂度 \(\operatorname{O}(\max(m,\cfrac pm))\) ，则 \(m=\sqrt p\) 时最优，复杂度是一个根号。

实现

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

read(n, p);
b = 10;
n = n * 9 + 1;

b = (b % p + p) % p;
n = (n % p + p) % p;

if (b == 0) {
	if (n == 0) output(1);
	failed();
}
if (n == 1) {
	output(0);
}
if (b == 1) {
	failed();
}

i128 m = sqrt(p), z = n;
for (i128 i = 0; i < m; ++i) {
	mp[z] = i; // 存储的实际上是模数所对应的最大 r（从小到大枚举，挨个覆盖）
	z = z * b % p;
}
z = binpow(b, m);
for (i128 i = 1, pian = z; i <= p / m + 10; ++i) {
	auto it = mp.find(z);
	if (it != mp.end()) {
		output(m * i - it->second);
	}
	z = z * pian % p;
}
failed();