BSGS算法
目录
- 离散对数问题（DLP）简介
- BSGS算法
- 结合Pohlig–Hellman 攻击
- EXBSGS算法
- BSGS在lcg中的应用
一、DLP简介
离散对数的定义与对数类似：
取有原根的正整数模数m，设其一个原根为g。由原根的定义，我们知道对满足$(a,m)=1$的整数a，必定存在唯一的整数k，$0\leq k<\varphi(m)$ ,使得
\[g^{k}\equiv a \ \ mod \ \ m\]我们称这个k为以g为底，模m的离散对数，记作$k=ind_{g}a$ .
关于离散对数的性质：
- $ind_{g}1=0,ind_{g}g=1$
- $ind_{g}(ab)\equiv ind_{g}a+ind_{g}b \ \ mod \ \ \varphi(m)$
- $ind_{g}a^{n}\equiv n ind_{g}a\ \ mod \ \ \varphi(m)$
- 若$g_{1}$也是模m的原根，则$ind_{g}a\equiv ind_{g_{1}}a\cdot ind_{g}g_{1}\ \ mod \ \ \varphi(m)$
- $a\equiv b \ \ mod \ \ m \iff ind_{g}a=ind_{g}b$
关于给定的g和a，求唯一的指数k使$g^{k}\equiv a \ \ mod \ \ m$ ,这就是离散对数问题（DLP）.
目前还不存在多项式时间内求解离散对数问题的算法。
为什么要使用原根？因为原根是 $\mathbb{Z}^{\times}_{m}$ 的生成元，所以原根的次幂，与${ 1,2,\dots,p-1 }$中的数字一一对应，这样才能进行加密和解密。
二、BSGS算法
大步小步算法（Baby-step Giant-step），简称BSGS。是一种能较快速求解离散对数问题的算法，可以在$O(\sqrt{ m })$ 的时间内求解
\[a^{x}\equiv b \ \ mod \ \ m\]其中$(a,m)=1$.
算法描述
将指数写成$x=\lceil \sqrt{ m } \rceil i-j$ 的形式，其中$0\leq i,j\leq \lceil \sqrt{ m } \rceil$ ,则
\(a^{\lceil \sqrt{ m } \rceil i-j} \equiv b \ \ mod \ \ m\) \(a^{\lceil \sqrt{ m } \rceil i} \equiv ba^{j} \ \ mod \ \ m\)
算法分为大步和小步两步
小步：枚举 j，计算所有$ba^{j}$ ,并用哈希表存下来
大步：逐一枚举 i，计算$a^{\lceil \sqrt{ m } \rceil i}$ ,若其出现在哈希表中，则得到这样的x。
输出$x=\lceil \sqrt{ m } \rceil i-j$ .
注意到 i , j 均小于$\lceil \sqrt{ m } \rceil$ 所以时间复杂度为$O(\sqrt{ m })$
为什么算法需要$(a,m)=1$ 呢？这是因为我们得到的 i , j 满足 $a^{\lceil \sqrt{ m } \rceil i} \equiv ba^{j} \ \ mod \ \ m$ ,若想让它同时满足$a^{\lceil \sqrt{ m } \rceil i-j} \equiv b \ \ mod \ \ m$ ，需要两边同时除以 $a^{j}$ .
算法实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def bsgs(g, h, m):
order = phi(m)
step = math.isqrt(order) + 1
g_inv = pow(g, -1, m)
g_neg_step = pow(g_inv, step, m)
table = {}
beta = 1
for j in range(step):
table[beta] = j
beta = (beta * g) % m
gamma = h
for i in range(step):
if gamma in table:
j = table[gamma]
return i * step + j
gamma = (gamma * g_neg_step) % m
return None
三、结合Pohlig–Hellman 攻击
当模数光滑时，可以对模数做分解以降低算法的复杂度。
先来回顾一下Pohlig–Hellman 攻击，设群 $G$ 的阶n有完全素因子分解： \(n = \prod_{i=1}^{k} p_i^{e_i}\)
离散对数问题：已知 $g,h\in G$，求 $x$ 使 $h=g^x$，其中 $0\le x < n$。
Pohlig–Hellman的做法是分别求出 \(x \bmod p_i^{e_i},\quad i=1,\dots,k\) 然后用中国剩余定理合成 $x \bmod n$。
每个模 $p_i^{e_i}$ 的求解过程又被进一步降解为多个模 $p_i$ 的小离散对数问题，这些模 $p_i$ 的小 DLP 就可以用 BSGS 快速求解。
攻击的详细步骤
2.1 计算每个素因子幂对应的生成元和目标元素
对于每个因子 $q = p_i^{e_i}$：
- 令 $g_q = g^{n/q}$，$h_q = h^{n/q}$。
- 此时 $g_q$ 的阶恰好为 $q$，且 $h_q = g_q^{x_q}$，其中 $x_q \equiv x \pmod{q}$（因为 $g_q$ 的阶为 $q$）。
于是问题化为求 $x_q$ 满足 $h_q = g_q^{x_q}$，$0\le x_q < q$。
2.2 若 $e_i = 1$（即 $q=p_i$ 为素数）
此时直接用 BSGS求 $x_q$。子群的规模为 $p_i$，BSGS 的复杂度为 $O(\sqrt{p_i})$。
2.3 若 $e_i > 1$（素数次幂情形）
需要用 Hensel 提升 将模 $p_i^{e_i}$ 的问题降解为多个模 $p_i$ 的 BSGS 求解。以 $q = p^e$ 为例：
设 $x \bmod p^e$ 可表示为 $p$ 进制展开： \(x \equiv x_0 + x_1 p + x_2 p^2 + \dots + x_{e-1} p^{e-1} \pmod{p^e}\) 其中每个 $x_j \in {0,\dots,p-1}$。
求 $x_0$（即 $x \bmod p$）：
令 $g_0 = g^{n/p}$（阶 $p$），$h_0 = h^{n/p}$。
则 $h_0 = g_0^{x_0}$。用 BSGS 解出 $x_0$。求 $x_1$ (即 $x-x_{0}\equiv x_{1}p \ \ mod \ \ p^2$)：
构造 $h_1 = (h \cdot g^{-x_0})^{\frac{n}{p^2}}$，$g_{1}=g^{\frac{n}{p}}$，$mod\ \ p^2$ 下，有
\[g_{1}^{x_{1}}=g^{\frac{n}{p^2}x_{1}p}=g^{\frac{n}{p^2}(x-x_{0})}=(h \cdot g^{-x_0})^{\frac{n}{p^2}}\]可得 $h_1 = g_1^{x_1}$。用 BSGS 解出 $x_1$。
依此类推，每次剥离已求出的低位，将问题降维成模 $p$ 的 DLP，最终得到完整的 $x \bmod p^e$。
2.4 中国剩余定理合成
求出所有 $x_i \equiv x \pmod{p_i^{e_i}}$ 后，使用 CRT 得到： \(x \equiv x_i \pmod{p_i^{e_i}},\; \forall i \quad\Longrightarrow\quad x \bmod n.\)
四、扩展BSGS
算法描述
当$(a,m)\neq1$时，要想办法将其变得互素。
具体地，设 $d_1=(a,m)$。如果 $d_1 \nmid b$，则原方程无解。否则我们把方程同时除以 $d_1$，得到
\[\frac{a}{d_1}\cdot a^{x-1}\equiv \frac{b}{d_1}\pmod{\frac{m}{d_1}}\]如果 $a$ 和 $\frac{m}{d_1}$ 仍不互质就再除，设 $d_2=(a,\frac{m}{d_1})$。如果 $d_2 \nmid \frac{b}{d_1}$，则方程无解；否则同时除以 $d_2$ 得到
\[\frac{a^2}{d_1d_2}\cdot a^{x-2}\equiv \frac{b}{d_1d_2}\pmod{\frac{m}{d_1d_2}}\]同理，这样不停的判断下去，直到 $(a, \frac{m}{d_1d_2\cdots d_k})=1$。
记 $D=\prod_{i=1}^{k}d_i$，于是方程就变成了这样：
\[\frac{a^k}{D}\cdot a^{x-k}\equiv \frac{b}{D}\pmod{\frac{m}{D}}\]由于 $(a, \frac{m}{D})=1$，于是推出 $(\frac{a^k}{D}, \frac{m}{D})=1$。这样 $\frac{a^k}{D}$ 就有逆元了，于是把它丢到方程右边，这就是一个普通的 BSGS 问题了，于是求解 $x-k$ 后再加上 $k$ 就是原方程的解。
注意，不排除解小于等于 $k$ 的情况，所以在消因子之前做一下 $O(k)$ 枚举，直接验证 $a^i\equiv b\pmod m$，这样就能避免这种情况。
算法实现
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
from math import gcd, isqrt
import sys
def exbsgs(a, b, m):
a %= m
b %= m
if m == 1:
return 0
if b == 1:
return 0
k = 0
d = 1
while True:
g = gcd(a, m)
if g == 1:
break
if b % g:
return -1
b //= g
m //= g
d = d * (a // g) % m
k += 1
if d == b:
return k
t = b * pow(d, -1, m) % m
ans = bsgs(a, t, m)
if ans == -1:
return -1
return ans + k
for line in sys.stdin:
if not line.strip():
continue
a, b, m = map(int, line.split())
print(exbsgs(a, b, m))
五、BSGS在lcg中的运用
lcg（线性同余生成器）指的是由
\[\begin{align} &X_{0}=seed \\ &X_{n+1}=aX_{n}+b \ \ mod\ \ m \end{align}\]生成的一系列随机数
现在来看这样一个问题：
[!question] 求最小的正整数$N$ , 使得$11\dots1(N个1)\equiv 114514 \ \ mod \ \ 10000000000099$
这样的数显然可以由lcg生成：
\[\begin{align} &X_{0}=0 \\ &X_{n+1}=10X_{n}+1 \ \ mod\ \ p \end{align}\]事实上，这个问题可以转换成离散对数问题：
将$X_{n}$展开得
\[X_{n}=a^{n}X_{0}+b(1+a+\dots a^{n-1}) \ \ mod \ \ p\] \[X_{n}=a^{n}X_{0}+b\frac{1-a^{n}}{1-a} \ \ mod \ \ p\] \[(a-1)X_{n}+b=a^{n}(X_{0}(a-1)+b)\ \ mod \ \ p\]显然，$(X_{0}(a-1)+b,p)=1$, 令$t=((a-1)X_{n}+b)(X_{0}(a-1)+b)^{-1} \ \ mod \ \ p$
\[a^n=t \ \ mod \ \ p\]变为求解n的离散对数问题。
代码：
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
import math
def bsgs(a, X, m):
M = math.isqrt(m) + 1
inv_a = pow(a, -1, m)
baby = {}
cur = X
for j in range(M):
if cur not in baby:
baby[cur] = j
cur = (cur * inv_a) % m
stride = pow(a, M, m)
cur = 1
for i in range(M + 1):
if cur in baby:
j = baby[cur]
return i * M + j
cur = (cur * stride) % m
return -1
def solve():
m = 10000000000099
a = 10
b = 1
x1 = 1
t = 114514
D = (x1 * (a - 1) + b) % m
C = (t * (a - 1) + b) % m
inv_D = pow(D, -1, m)
X = (C * inv_D) % m
if X == 0:
print(-1)
return
k = bsgs(10, X, m)
if k == -1:
print(-1)
else:
N = k + 1
print(f"N = {N}")
if __name__ == "__main__":
solve()
参考：