跳转至

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，从而我们可以得到所有的 x， x=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，则称 t是 a模 p意义下的次数，若 t=\varphi(p)，则称 a是 p的原根。

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

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

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

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

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

PROOF

记 d = tq+r， 0 \le r < t.

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

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

\therefore r = 0.

即 d = tq， t \mid d

Q.E.D.

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

于是可以得到一种基于 原根分布 的算法来找原根，首先把 p-1的因数全部求出来，然后从 2到 p-1枚举，判断是否为原根，如果对于数 g， \exists g^t \equiv 1 \bmod p， t是 p-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，这样就能避免这种情况。

build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

评论