离散对数（BSGS）

离散对数问题，即已知 $𝑎, 𝑏, 𝑝$ ，求方程 $𝑎 𝑥 \equiv 𝑏 (m o d 𝑝)$ 最小非负整数解。

BSGS 算法

原理

思考暴力做法，即枚举 $𝑥$ 直到满足方程，复杂度 $O (𝑝)$

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

首先把 $𝑥$ 拆开，拆成 $𝑘 𝑚 - 𝑟$ ，然后进行变换： $𝑎 𝑥 \equiv 𝑏 (m o d 𝑝) 𝑎 𝑘 𝑚 - 𝑟 \equiv 𝑏 (m o d 𝑝) 𝑎 𝑘 𝑚 𝑎 𝑟 \equiv 𝑏 (m o d 𝑝) 𝑎 𝑘 𝑚 \equiv 𝑏 𝑎 𝑟 (m o d 𝑝)$ 这里的 $𝑚$ 我们设为一个固定值，然后分别枚举等式两边的 $𝑘, 𝑟$ ，存哈希表（映射），然后匹配即可，其中 $𝑘 \in [0, 𝑝 𝑚], 𝑟 \in [0, 𝑚]$ ，复杂度 $O (m a x (𝑚, 𝑝 𝑚))$ ，则 $𝑚 = \sqrt 𝑝$ 时最优，复杂度是一个根号。

实现

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();

复制

本文采用 GNU 自由文档许可证许可协议，转载请注明出处。