跳转至

BSGS

大步小步算法

基础篇

大步小步算法英文名:baby-step gaint-step (BSGS).

该算法可以在 O(\sqrt{q})用于求解

a^x \equiv b \bmod p

其中 p是个质数的方程的解 x满足 0 \le x < p.

x = A \lceil \sqrt p \rceil - B,其中 0\le A,B \le \lceil \sqrt p \rceil

则有 a^{A\lceil \sqrt p \rceil -B} \equiv b,稍加变换,则有 a^{A\lceil \sqrt p \rceil} \equiv ba^B.

我们已知的是 a,b,所以我们可以先算出等式右边的 ba^B的所有取值,枚举 B,用 hash/map 存下来,然后逐一计算 a^{A\lceil \sqrt p \rceil},枚举 A,寻找是否有与之相等的 ba^B,从而我们可以得到所有的 xx=A \lceil \sqrt p \rceil - B.

注意到 A,B均小于 \lceil \sqrt p \rceil,所以时间复杂度为 O(\sqrt q),用 map 的话会多一个 \log.

BZOJ-2480是一道模板题(可能是权限题),BZOJ-3122是一道略加变化的题,代码可以在Steaunk 的博客中看到。

略微进阶篇

求解

x^a \equiv b \bmod p

其中 p是个质数。

该模型可以通过一系列的转化为成基础篇中的模型,你可能需要一些关于原根的概念。

原根的定义为:对于任意数 a,满足 (a,p)=1,且 t为最小的正整数满足 a^t \equiv 1 \bmod p,则称 tap意义下的次数,若 t=\varphi(p),则称 ap的原根。

首先根据原根存在的条件,对与所有的素数 p>2和正整数 e,当且仅当 n=1,2,4,p^e,2p^e时有原根,

那么由于式子中的模数 p,那么一定存在一个 g满足 gp的原根,即对于任意的数 x在模 p意义下一定有且仅有一个数 i,满足 x = g^i,且 0 \le x,i < p.

所以我们令 x=g^cgp的原根(我们一定可以找到这个 gc),则为求 (g^c)^a \equiv b \bmod p的关于 c的解集,稍加变换,则有 (g^a)^c \equiv b \bmod p,于是就转换成了我们熟知的BSGS的基本模型了,即可在 O(\sqrt p)解决。

那么关键的问题就在于如何找到这个 g了?

关于对于存在原根的数 p有这样的性质:若 tap的次数(这里蕴含了 (a,p)=1),那么对于任意的数 d,满足 a^d \equiv 1 \bmod p,则 t \mid d.

PROOF

d = tq+r0 \le r < t.

\because a^d \equiv a^{xq+r} \equiv (a^t)^qa^r \equiv a^r \equiv 1.

\because 0 \le r < ttap的次数,即 t是最小的正整数满足 a^t \equiv 1.

\therefore r = 0.

d = tqt \mid d

Q.E.D.

由此当 p是质数的时候还有这样的推论:如果不存在小于 p且整除 p-1正整数 t, 满足 a^t \equiv 1,那么又根据费马小定理,有 a^{p-1} \equiv 1,所以 p-1ap的次数,即 ap的原根。

于是可以得到一种基于原根分布的算法来找原根,首先把 p-1的因数全部求出来,然后从 2p-1枚举,判断是否为原根,如果对于数 g\exists g^t \equiv 1 \bmod ptp-1的因数,则 g一定不是 p的原根。

看上去复杂度好像很爆炸(可能确实是爆炸的,但一般情况下,最小的原根不会很大)。

基于一个假设,原联系根是均匀分布的,我们伪证明一下总复杂度:原根数量定理:数 p要么没有原根,要么有 \varphi(\varphi(p))个原根。

由于 p是质数,所以 p\varphi(p-1)个原根,所以大概最小的原根为 \frac{p}{\varphi(p-1)}=O(\log\log n),由于求每一个数时要枚举一遍 p-1所有的因数 O(\sqrt p)来判断其是否为原根,最后再算上BSGS的复杂度 O(\sqrt{p}),则复杂度约为 O(\sqrt{p}\log \log n).

BZOJ-1319是一道模板题,代码可以在Steaunk 的博客中看到。

扩展篇

上文提到的情况是 c为素数的情况,如果 c不是素数呢?

这就需要用到扩展 BSGS 算法,不要求 c为素数!

扩展 BSGS 用到了同余的一条性质:

d=gcd(a,c) ,a=m \times d,b=n \times d,p=k \times d; 则 m \times d \equiv b \times d \pmod {c \times d}等价于 m \equiv n \pmod k所以我们要先消除因子:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
d = 1, num = 0, t = 0;
for (int t = gcd(a, c); t != 1; t = gcd(a, c)) {
  if (b % t) {
    \\无解
  }
  b /= t;
  c /= t;
  d *= a / t;
  num++;
}

消除完后,就变成了 d \times m^{x-num} \equiv n \pmod k,令 x=i \times m+j+num,后面的做法就和普通 BSGS 一样了。

注意,因为 i,j \le 0,所以 x \le num,但不排除解小于等于 num的情况,所以在消因子之前做一下 \Theta(\log_2 p)枚举,直接验证 a^i \mod c = b,这样就能避免这种情况。


评论