BSGS和扩展BSGS 学习笔记

口胡一下 $\mathrm{BSGS}$ 和 $\mathrm{exBSGS}$

你们怎么都那么熟练啊？

不对的地方欢迎指错。

BSGS

$\mathrm{BSGS}$ 是用来求满足 $a^x\equiv b(\mathrm{mod}\;p)$ ($p$ 是质数) 的 $x$ 的最小值的基础数论算法。

首先考虑方程是否有解即 $a,p$ 是否互质，又因为 $p$ 是质数，所以$a,p$是否互质等同于 $a$ 是否是 $p$ 的倍数。

然后我们把 $x$ 拆成 $i*m-j$，其中$m=\lceil\sqrt p\rceil$，代入到 $a^x\equiv b(\mathrm{mod}\;p)$ 中

得到 $a^{i*m-j}\equiv b(\mathrm{mod}\;p)$

根据同余的性质得到 $a^{i*m} \equiv b*a^j(\mathrm{mod}\;p)$

然后就可以

从 $0\backsim m$ 枚举 $j$，把计算出的 $(b*a^j) \mathrm{mod}\;p$ 存入 $\mathrm{hash\_table}$ 中
从 $1\backsim m$ 枚举 $i$，在 $\mathrm{hash\_table}$ 查找是否存在 $a^{i*m} \mathrm{mod}\;p$
- 若存在则此时的 $i*m-j$ 为最小值
- 若不存在则继续枚举下去

时间复杂度$\mathrm{O}(m*\mathrm{hash\_table})$

TIPS: 还有一种做法是令 $x=i*m+j$，这样的话除过去会牵扯到逆元，上面的做法可以完美避开逆元。

$\mathrm{hash\_table}$ 一般用std::map 来实现，想要更高效的话可以手写 $\mathrm{hash\_table}$，比如 $\mathrm{SDOI2013}$随机数生成器，map不开O2会T，但手写的话就会快的飞起。

~~本来想先坑着，想想还是填上吧~~

$\mathrm{exBSGS}$ 是用来求满足 $a^x\equiv b(\mathrm{mod}\;p)$ 的 $x$ 的最小值的基础数论算法。（注意这里的 $p$ 不要求是质数）

我们令 $g_1=gcd(a,p)$。

不满足上面的两条，我们就要用 $\mathrm{exBSGS}$ 了。

根据同余的性质，我们在方程两边同时除以 $g_1$，得到

\[a^{x-1}*\frac a {g_1}\equiv \frac b {g1}(\mathrm{mod}\;\frac p {g_1})\]

此时 $a$ 与 $\Large\frac p {g_1}$ 可能仍然不互质，我们继续分解下去

令 $g_2=gcd(a,\Large\frac p {g_1})$

然后我们就可以发现很神奇的事情，令 $b’={\Large \frac b {g_1}},p’=\Large \frac p {g_1}$，这样方程就变成了

\[a^{x-1}*\frac a {g_1}\equiv b'(\mathrm{mod}\;p')\]

好像可以递归下去啊（再回到1和2的判断），写份伪代码爽一下

while(true) {
	ll g=gcd(a,p);
	if(b%g!=0) return b==1?0:-1;
	if(g==1) return bsgs(a,b,p);
	b/=g,p/=g;
}

但是这样好像不能处理 $\equiv$ 左边 $a$ 的那部分，想办法处理一下。

$a^{x-1}$这部分很好处理，我们把 $\Large\frac a {g_1}$ 这部分乘起来，用 $c$ 表示

那最后的方程就变成了 $c*a^{x-1}\equiv b’(\mathrm{mod}\;p’)$，这个 $x-1$ 好像有点钦定的意思啊，不一定只分一次啊，我们再把 $x-1$ 换成 $x-k$

那最后的方程就是 $c*a^{x-k}\equiv b'(\mathrm{mod}\;p')$

然后再利用和 $\mathrm{BSGS}$ 一样的处理方法去做就好了。

一些细节