【学习笔记】BSGS 算法

本文主要是介绍【学习笔记】BSGS 算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

引入

BSGS（baby-step giant-step），即大步小步算法，常用于求解离散对数问题。该算法可以在 \(O(\sqrt p)\) 的时间复杂度内求解

\[a^x \equiv b \pmod p \]

第一部分：\(a \perp p\)

我们将求解的答案 \(x\) 设为 \(km-c \ (c < m)\) 的形式，即

\[a^{km-c} \equiv b \pmod p \]

在 \(a \perp p\) 条件下，上式等价于

\[a^{km} \equiv ba^{c} \pmod p \]

先枚举 \(c\)，使用哈希表（或 map）将所有 \(ba^c\) 的值存起来。

再枚举 \(k\)，计算 \(a^{km}\) 的值并寻找是否有 \(ba^c\) 的值与之对应，从而找到方程所有解。

至此，我们找到了模 \(p\) 意义下的所有解。

不难发现，该算法时间复杂度为 \(O(\max (m,\dfrac{p}{m}))\)，当 \(m=\left\lceil \sqrt p \right\rceil\) 时，复杂度最优。

故该算法的时间复杂度为 \(O(\sqrt p)\)。

第二部分: \(a,p\) 不互素

此时，\(a^{km} \equiv ba^{c} \pmod p\) 是 \(a^{km-c} \equiv b \pmod p\) 的必要不充分条件，我们需要进行变形使得 \(a\) 和模数以使用上述算法求解。

同余的基本性质：若 \(a,b,d,m \in \mathbf{N^*},d \mid a,d \mid b,d \mid m\)，则 \(a \equiv b \pmod p\) 等价于 \(\frac{a}{d} \equiv \frac{b}{d} \pmod {\frac{m}{d}}\)

设 \(d_1=\gcd(a,p)\)。

若 \(d_1 \nmid b\)，则方程无解。

否则，将方程变形为

\[\dfrac{a}{d_1}a^{x-1} \equiv \dfrac{b}{d_1} \pmod {\dfrac{p}{d_1}} \]

若 \(a\) 与 \(\dfrac{p}{d_1}\) 仍不互素，则不断重复上述过程，直到 \(a \perp \dfrac{p}{d_1d_2 \cdots d_m}\)。

此时，原方程变形为

\[\dfrac{a^m}{d_1d_2 \cdots d_m}a^{x-m} \equiv \dfrac{b}{d_1d_2 \cdots d_m} \pmod {\dfrac{p}{d_1d_2 \cdots d_m}} \]

通过第一部分的 BSGS 算法，不难求出 \(x-m\) 的所有解，只需另外需考虑 \(x < m\)的情况即可。

时间复杂度仍为 \(O(\sqrt n)\)

离散对数

设 \(g\) 是模 \(n\) 的原根，那么对于任意 \(a\) 满足 \(a \perp n\)，均存在 \(k\) 使得

\[g^k \equiv a \pmod n \]

这样的关系有助于把 \(\bmod \ n\) 的乘法转化为 \(\bmod \ \varphi(n)\) 的加法。

考虑求解 \(x^a \equiv b \pmod p\)，满足 \(b \in \mathbf{N^*}\) 且 \(p\) 是素数。

设 \(g\) 为模 \(p\) 的原根，由于 \(g^0,g^1,g^2,\cdots,g^{p-2}\) 构成模 \(p\) 的一组简化剩余系且 \(p \nmid x\)，故令 \(x=g^c,b=g^t\)，得到

\[g^{ac} \equiv g^t \pmod p \]

两边同时取离散对数，得到

\[ac \equiv t \pmod {\varphi(p)} \]

我们可以先通过 BSGS 算法求解出 \(t\)，再通过扩展欧几里得算法求解出 \(c\)，即可得到方程的一组特解：\(x_0=g^c\)。

找到一组特解 \(x_0=g^c\) 之后，令 \(x=g^k\)，得到

\[g^{a \cdot k} \equiv g^{a \cdot c+t \cdot \varphi(p)} \pmod p \]

故 \(k\) 的所有解为

\[\forall t \in \mathbf Z,a \mid t \cdot \varphi (p),k=c+ \dfrac{t \cdot \varphi(p)}{a} \]

由于 \(a \mid t \cdot \varphi (p)\)，则 \(\frac{a}{\gcd(a,\varphi (p))} \mid t\)，故令 \(t=\frac{a}{\gcd(a,\varphi (p))} \cdot i\)

则原方程所有解为

\[\forall i \in \mathbf Z,x=g^{c+ \frac{\varphi (p)}{\gcd(a,\varphi (p))} \cdot i} \]

参考资料

• OI WiKi BSGS
• BSGS 算法

这篇关于【学习笔记】BSGS 算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！