发布于 ,更新于 

离散对数(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();