扩展 BSGS 学习笔记

标签：pmod dfrac 扩展 笔记 cdot perp BSGS equiv

在 之前 ，我们学习了 BSGS 。

设有 \(a,b,m\) ，且 \((a,m)\ne1\) ，求解：

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

这玩意如何求解？把它变成 BSGS 能做的形式不就行了！

具体的，设 \(d_1=(a,m)\) ，若\(d_1\not|b\) 则方程无解。否则我们可以得到：

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

如果 \(a\) 与 \(\dfrac{m}{d_1}\) 不互质就继续处理。设 \(D=\prod d\) ，则继续处理直到 \(a\perp\dfrac{m}{D}\) 。

也就是说，原式可以化为：

\[\dfrac{a^k}{D}\cdot a^{x-k}\equiv\dfrac{b}{D}\pmod{\dfrac{m}{D}} \]

其中 \(k\) 为 \(d\) 的长度。可以推出 \(\dfrac{a^k}{D}\perp\dfrac{m}{D}\) ，把 \(\dfrac{a^k}{D}\) 丢到方程右边，得到：

\[a^{x-k}\equiv\dfrac{b}{a^k}\pmod{\dfrac{m}{D}} \]

这样就可以使用 BSGS 直接求出 \(x-k\) 的值了。

标签：pmod,dfrac,扩展,笔记,cdot,perp,BSGS,equiv
From： https://www.cnblogs.com/01bit/p/18334909