BSGS及其扩展

emptysetvvvv · 2019-05-31 18:25:45 · 个人记录

【概念】BSGS 算法求解方程 A^x\equiv B\pmod p的最小非负整数解，p 为素数。

1\ [BSGS]

【方法】
首先判断解的范围

由费马小定理 A^{p-1}\equiv 1\pmod p，可得

A^{\displaystyle x+k(p-1)}\equiv B\pmod p

那么如果方程有解，那么最小非负整数解x\in[0,p-1]

（比如 A^{p}\equiv A^1，x 取 p 还不如取 1）。

现在我们已经知道了 x\in[0,p-1]，接下来怎么做呢？

~~我会暴力！！~~ 枚举 i 从 0 至 p-1，判断 A^{i}\mod p 是不是 B，复杂度O(p)，而且很难化简这个式子降复杂度了。

接下来，就是 BSGS 的巧妙之处了

我们令 x=iq+j（就是 x 除以 q 等于 i，余 j ），q 是我们随便设置的一个定值，显然 j\in[0,q-1]。

则原式化为

A^{\displaystyle iq+j}\equiv B\pmod p

进一步化为

A^{\displaystyle iq}\equiv B\cdot A^{-j}

等一下，右边怎么会有A^{-j}？看着多麻烦啊。

改一下

这样吧，我们一开始改为令 x=iq-j，

这样最终就是

A^{\displaystyle iq}\equiv B\cdot A^{j}\pmod p

我们可以先用$O(q)$的时间枚举 $j$ 从 $0$ 到 $q-1$，将所有的$B\cdot A^j$标记出来。标记方法：$hash(B\cdot A^j)=j$。哦，我们知道了如果方程有解，那么$A^{iq}$一定可以取某个被标记的数。由于 $iq-j$ 最大为 $p-1$，即 $iq-1\leqslant p-1$，$i\leqslant \displaystyle \frac p q$，我们可以用$O(\displaystyle \frac p q)$的复杂度枚举 $A^{iq}$，看看他的值有没有标记过。第一次遇到 $hash(A^{\displaystyle iq})$ 被标记时，就可以知道现在的 $i$ 和 $j$ 满足 $x=iq-j$是方程的解。复杂度为$O(q+\displaystyle\frac p q)$，由基本不等式可知我们一开始设置$q=\lceil\sqrt p\rceil$可以取得最优复杂度$O(\sqrt p)$。 - 代码实现 $A^{\displaystyle iq}$ 作为下标过大，因此用哈希表或```map<int,int>```实现。 - 【代码】 ```cpp int BSGS(int A, int B, int p) { if(!A) return B ? -1 : 1; if(B == 1) return 0; Hash.clear(); const int q = ceil(sqrt(p)); for(int i = 0, j = B; i < q; i++, j = (ll)j * A % p) Hash[j] = i; A = power(A, q, p); for(int i = 1, j = A; i <= q; i++, j = (ll)j * A % p) if(Hash.count(j)) return i * q - Hash[j]; return -1; } ``` 注意，$iq-j$ 至少为$1$，因此要特判 $B=1$ 时解为$0$。 - 【链接】[BSGS 详解](http://www.orchidany.cf/2019/02/06/BSGS-junior/#more) - 【默示】BSGS全称 Baby Step Giant Step，枚举 $B\cdot A^j$ 称为小步，$A^{iq}$ 称为大步。这其中有一定的折半搜索的思想，不过折半搜索是对很明显的多个元素进行划分，标记左边，枚举右边查找。而北上广深算法将单独的 $x$ 进行拆解为两个元素，标记一侧，枚举另一侧查找，着实很巧妙。 ## $2\ [$ExBSGS$]

如果 p 不保证是素数呢？
【方法】
首先看 p 不是素数会有什么影响呢？

费马小定理的条件是A\perp p，可是现在A,p 都是任意非负整数（p\neq0），我们不能确定解的范围了。

想想办法使A\perp p

令 d_1=\gcd(A,p)，原方程可化为

\displaystyle \frac{A}{d_1}A^{x-1}\equiv {\frac{B}{d_1}}\pmod{\frac{p}{d_1}}

注意判断 B 不是 d_1 的倍数就无解（观察上式可知，或用裴蜀定理证明）。

若有解，不妨记为

D_1A^{x-1}\equiv {B_1}\pmod{p_1}

但此时 p_1 与 A 仍然不一定互质，因为只有 p 消去了 \gcd 变为 p_1，

没关系，我们令 d_2=gcd(A,p_1)，重复操作，直到 A\perp p_k，或者中途发现无解。

若有解，则最终化为这样的形式：

\displaystyle\prod_{i=1}^k \frac{A}{d_i}\cdot A^{x-k}\equiv B_k\pmod{p_k}

不妨记为

D_k\cdot A^{y}\equiv B_k\pmod {p_k}

现在我们可以用 BSGS 求解 y了，最终答案 x=y+k。
还要注意一点，

我们可以发现这样求解的 x 一定是大于等于 k 的，那么万一在[0,k-1]之间有解呢？

也很简单，在不断消 \gcd 的时候判断，D_i\cdot A^{x-i}\equiv B_i\pmod {p_i} 中若有D_i=B_i，则当前的i即为解。

复杂度O(\log p+\displaystyle\sqrt p)=O(\displaystyle\sqrt p).

【代码】

int ExBSGS(int A, int B, int p) {
          if(p == 1) return 0;
          if(!A) return B ? -1 : 1;
          if(B == 1) return 0;
          int d, k = 0, D = 1;
          while((d = gcd(A, p)) != 1) {
              if(B % d) return -1;
              B /= d, p /= d, D = (ll)D * A/d % p;
              k++; if(B == D) return k; 
          }
          Hash.clear();
          const int q = ceil(sqrt(p));
          for(int i = 0, j = B; i < q; i++, j = (ll)j * A % p) 
              Hash[j] = i;
          A = power(A, q, p);
          for(int i = 1, j = (ll)D * A % p; i <= q; i++, j = (ll)j * A % p)
              if(Hash.count(j)) return i * q - Hash[j] + k;
          return -1;
}