Java教程

【学习笔记】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 算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!