数论 - BSGS 算法推导

写在前面（的废话）

BSGS 的用途是解离散对数，复杂度 $\sqrt{n}$
主要参考了 hzwer 和 clover_hxy 的文章。

但是貌似 hzwer 的那篇不太容易懂，clover_hxy 的这个坠吼了。

其他的一些补充：离散对数这类问题没有快速解法，所以说可以用来做公钥加密 （ElGamal，特地咨询了 Asterisk）

那么 BSGS 呢？其实也是属于一种密码学攻击手段，叫做 Meet-in-the-middle attack， 属于用空间换时间，最早是针对 DES-3 的。

BSGS 推导

求 $y^x \equiv z \pmod{p}$
设一个常数 $m$ ，令 $x = im - j$
有 $y^{im-j} \equiv z \pmod{p}$
有 $y^j z \equiv y^{im} \pmod{p}$

那么可以通过预处理所有的 $y^j z ,\quad j \in [0, m]$ 存到一个数据结构中 （比如蛤希表），枚举 $i \in [1, m]$ 计算 $y^{im}$ 来求解。

最终答案就是 $x = im - j$

显然 $m = \lceil \sqrt{p} \rceil$ 坠吼

一点问题

$x = im - j, \quad i \in [1, m], \quad j \in [0, m]$ 所以说 $x \le p$ ， 如何保证这里面一定有解？

可以证明 $x \in [0, p-1]$ 用到费马小定理的一个结论

$$a^{k \bmod p-1} \equiv a^{k} \pmod{p}$$

$k \bmod p-1$ 可以看作 $k - m(p-1)$ ，原式化为

$$\frac{a^k}{[a^{(p-1)}]^m} \equiv a^k \pmod{p}$$

根据费马小定理 $a^{(p-1)} \equiv 1 \pmod{p}$ （其中 $p$ 为指数，$\gcd (a, p) = 1$）得到

$$\begin{align} \frac{a^k}{1^m} & \equiv a^k & \pmod{p} \\ a^k & \equiv a^k & \pmod{p} \end{align}$$

总结 BSGS 的一般形式

求解离散对数问题 $y^x \equiv z \pmod{p}$ 求最小 $x$
令 $m = \lceil \sqrt{p} \rceil$ ， $x = im - j$
得到 $y^{im-j} \equiv z \pmod{p}$ 即 $y^j z \equiv y^{im} \pmod{p}$
预处理所有的 $y^j z ,\quad j \in [0, m]$ ，枚举 $i \in [1, m]$ 计算 $y^{im}$ ， 求最小的满足上式的 $i$
此时 $x = im - j$