BSGS && EXBSGS

基础BSGS

用处是什么呢w

大步小步发(Baby-Step-Giant-Step，简称BSGS)，可以用来高效求解形如$A^x≡B(mod C)$(C为素数)的同余方程。

常用于求解离散对数问题。形式化地说，该算法可以在$O(\sqrt{n})$用于求解。

接下来是算法过程

首先我们讨论的都是(A,C) = 1(由于C是素数，所以等价于A不是C倍数)的情况，如果(A,C) > 1(A是C倍数)，很容易特判掉。

先引入一个结论:

如果(A,C) = 1,那么对于$x \in N$,有$A^{x mod \phi(C)} ≡ A^x (mod C)$

如下证明过程：

因为(A,C) = 1,根据欧拉定理，可得$A^{k * \phi(C)} ≡ 1 (mod C)$

设$k \in N$,根据同幂性，$A^{k * \phi(C)} ≡ 1 (mod C)$

设$a \in N$ 且 $a < \phi(C)$,所以$A^x(mod C)$,得证。

所以如果$0 \leq x < \phi(C)$无解，之后肯定也无解，但是$\phi(C)$并一定是最小正周期。

其算法本质是根号分治，令$m=[\sqrt{C}]$,我们假设x = i * m - j,其中$0 \leq i,j \leq m$,则有$A^{i*m - j} ≡ B$ ,稍加变换,可以得到$A^{i*m}≡B*A^j$

我们现在已知的是$A,B$,所以我们可以先通过枚举j,算出$B * A^j$,用hash/map存下来，然后再枚举i，计算出$A^{i * m}$寻找是否有与之相等的$B * A^j$,从而我们可以得到所有的$x$，$x = i * m - j$

因为i,j都小于等于m，所欲复杂度为$ Θ(\sqrt{C})$,用map多一个log

进阶BSGS

问题：求解$x^a ≡ b$ $mod$ $p$ (p为质数)

这个问题可以通过转化变成上面基础BSGS中所说的样子

因为$p$是一个质数，所以$p$一定存在一个原根$g$，因此在模$p$的意义下的任何数$x$，有且只有一个数$i$满足$x = g^i$

方法一：

令$x = g^c$,$g$是$p$的原根(肯定存在这个g和c)，问题转化为求解$(g^c)^a ≡ b$ $mod$ $p$ ，可以转化为

$(g^a)^c ≡ b (mod p)$

这就转化为基础篇中我们所说的内个式子了，可以在$O(\sqrt{p})$解出$c$，这样可以得到原方程的一个特解 $x_0 ≡ g^c$ $mod$ $p$

方法二：

我们仍令$x = g^c$，并且设$b = g^t$，于是乎我们得到 $g^{ac}≡ g^t$ $mod$ $p$

方程两边同时取离散对数可以得到 $ac ≡ t$ $mod$ $\phi(p)$

这样我们可以通过BSGS求解$g^t ≡ b$ $mod$ $p$得到$t$，于是这就转化成为一个线性同余方程问题，这样也可以解出$c$，求出$x$的一个特解$x_0 = g^c ≡ b$ $mod$ $p$

如果要找到$x$的所有解而不是特解的话：

我们能求出一个特解$x_0 ≡ g^c (mod$ $n)$，我们知道$g^{\phi(n)} ≡ 1 (mod$ $n)$，于是可以得到下面这个式子，
\[
\forall t \in Z,x^k ≡ g^{c*k+t*\phi(n)} ≡ a (mod p)$
\]

于是得到所有解为
\[
\forall t \in Z ,k|t * \phi(n),x ≡ g^{c+\frac{t * \phi(n)}{k}} ≡ a (mod p)
\]

然后对于上面这个式子有$\frac{k}{gcd(k,\phi(n))}|t$。因此我们设$t = \frac{k}{gcd(k,\phi(n))}*i$，可以得到

\[
\forall i \in Z,x ≡ g^{c + \frac{\phi(n)}{gcd(k,\phi(n))} * i} (mod p)
\]

这就是原问题的所有解

下面是EXBSGS

与BSGS相类似，这个算法也是解决$a^x≡b(mod p)$的问题，只不过C可以不是质数。

我们知道，在$a$与$p$互质的时候，在模$p$的意义下$a$存在逆元，我们就可以用BSGS来解决问题，那么在他们不互质的情况下，我们就要使他们变成互质的。

具体来说，我们设$d_i = gcd(a,p)$，如果$d_1$不是b的因子，那么原方程无解，有解的情况下我们将方程两边同时处以$d_1$，可以得到
\[
\frac{a}{d_1} * a^{x - 1}≡\frac{b}{d_1} mod \frac{p}{d_1}
\]
如果$a$和$\frac{p}{d_1}$仍然不互质的话设$d_2 = gcd(a,\frac{p}{d_1})$。如果$d_2$不是$\frac{b}{d_1}$，则方程无解，有解的情况下将方程两边同时除以$d_2$，得到
\[
\frac{a^2}{d_1d_2} * a^{x - 2} ≡ \frac{b}{d_1d_2} mod \frac{p}{d_1d_2}
\]
同理，我们不停地这样判断，直到$a$与$\frac{p}{d_1d_2...d_k}$互质为止。

设$D = \prod_{i = 1}^{k} d_i$，于是方程就变成了下面这样：
\[
\frac{a^k}{D} * a^{x - k} ≡ \frac{b}{D} mod \frac{p}{D}
\]
因为$a$与$\frac{p}{D}$互质，于是可是推出$\frac{a^k}{D}$与$\frac{p}{D}$互质，这样的话$\frac{a^k}{D}$就有逆元了，于是把它移到方程的右边，这就变成了一个BSGS问题，于是求解$x - k$后再加上$k$就是原方程的解了。

值得注意的是，不排除解小于等于k的情况，所以咋消因子前应$O(k)$枚举，直接验证$a^i≡b$ $mod$ $p$，这样就能避免这种情况。

巴特西

BSGS && EXBSGS

最新文章

热门文章