手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

算法学习笔记(10): BSGS算法及其扩展算法

2023-01-16 14:07:30 来源：博客园

BSGS算法及其扩展算法

BSGS算法

所谓 Baby Step, Giant Step算法，也就是暴力算法的优化

(资料图)

用于求出已知 \(a, b, p\), 且 \(p\) 为质数时 \(a^x \equiv b \pmod p\) 的一个最小正整数解 \(x\)

下文中 \(a \perp p\) 指的是 \(a, p\) 互质

有两种情况：

\(a, p\) 不互质，又由于 \(p\) 是质数，意味着 \(a\) 是 \(p\) 的倍数，所以 \(b\) 如果不为 \(0\) ，那么一定无解
两者互质……即 \(a \perp p\) :

考虑到 \(a \perp p\) 意味着 \(a\) 在 \(p\) 的完全剩余系中，也就是说 \(f(x) = a^x \pmod p\) 是一个周期为 || (……就是 \(a\) 在模 \(p\) 意义下的生成子群的大小) 的周期函数

实际上我们不会算出其周期的具体大小，我们只需要利用 || 恒 \(\le p\) 就行了

那么我们只需要枚举 \(x \in [0, p)\) 依次验证就可以求解了

但是暴力枚举没有那么优秀，对于出题人的数据可能过不了

所以我们就可以采用~~把毒瘤出题人吊起来打的方法~~BSGS算法进行优化

BSGS算法采用分块的思想 ~~（分块？块大小就 \(\sqrt p\) 不就就行了吗，有什么好疑惑的？~~

假设块大小为 \(t\)

先参入 \(t\) 改写一下式子 \(a^x \equiv b \pmod p\)

得到 \(a^{it-j} \equiv b \pmod p\)

由于 \(a \perp p\) ，上述式子等价于 \(a^{it} \equiv (a^t)^i \equiv b a^j \pmod p\)

那么我们先预处理右式，枚举 \(j \in [0, t)\) 把 \(ba^j \mod p\) 插入到一个Hash表中

也就是说 \(HashMap: \quad ba^j\ mod\ p \Rightarrow j\)

那么枚举 \(i \in [0, \lceil \frac pt \rceil]\) 计算出 \(a^{it} \mod p\) ，查找是否有对应的 \(j\)，更新答案即可

时间复杂度为 \(O(t + \lceil \frac pt \rceil)\)

为了进一步优化时间复杂度，已知均值不等式 \(a + b \ge 2\sqrt{ab}\)，当且仅当 \(a=b\) 时等号成立，所以我们令 \(t = \lceil \sqrt p \rceil\)，那么时间复杂度就简化为了 \(O(\sqrt p)\)

常数为 \(2\) 可能还需要带一个 \(log\) ? QwQ

参考代码如下：~~仅供参考~~

templatedata BSGS(data a, data b, data p) {    b %= p;    static std::map hash; hash.clear();    data t = std::ceil(std::sqrt(p)), v(1), j(0);    for (; j < t; ++j) {        // 此时 v = a^j % p        hash[v * b % p] = j;        v = v * a % p;    }    // 把 a 预处理成 a^t, 这样 (a^t)^i 就可以更快的算出了    a = qpow(a, t, p), v = 1;    // 如果此时 a 已经为 0 了，由于 t < p， p为质数所以 p|a (a为p的倍数)    // 那么此时，如果 b 不为 0 则一定无解    if (a == 0) return b == 0 ? 1 : -1;    for (data s(0); s <= t; ++s) {        // 此时 v = (a^t)^s        j = hash.find(v) == hash.end() ? -1 : hash[v];        if (~j && s * t >= j) return s * t - j;        v = v * a % p;    }    return -1;}

扩展BSGS算法 (exBSGS)

其实问题一摸一样，只是 \(p\) 不为质数了，也就是说其中 \(a, p\) 不一定互质

那么我们需要想办法使之变得互质，然后通过普通的 BSGS算法求解

具体的，令 \(d_1 = gcd(a, p)\)，如果 \(d_1 \nmid b\) 则原方程无解

这个我们可以将同余式转换：\(s a^x + tp = b\)
左式再转化为 \(d_1 (s a^{x-1} \frac a{d_1} + t \frac p {d_1}) = b\)
也就是说，如果 \(d_1 \nmid b\) ，那么一定无整数解

那么上述式子就可以转化为 \(sa^{x-1} \frac a{d_1} + t \frac p {d_1} = \frac b {d_1}\)

再换成同余式子，就变为了 \(\frac a {d_1}\cdot a^{x-1} \equiv \frac b {d_1} \pmod {\frac p {d_1}}\)

如果此时 \(a\) 与 \(\frac p {d_1}\) 任然不互质，那么继续上述转化，令\(d_2 = gcd(a, \frac p {d_1})\)

则 \(\frac a {d_1 d_2} \cdot a^{x-2} \equiv \frac b {d_1 d_2} \pmod {\frac p {d_1 d_2}}\)

同理不断处理，直到 \(a \perp \frac p {d_1 d_2 \dots d_k}\)

我们记 \(D = \prod_{i = 1}^k d_i\)

那么最终的方程就是 \(\frac {a^k} {D} \cdot a^{x-k} \equiv \frac bD \pmod {\frac pD}\)

这样，我们把 \(\frac {a^k}D\) 通过逆元丢到方程右边，就成为了一个普通的 BSGS问题了

注意一个细节，不排除解小于等于 \(k\) 的情况，所以在消去 \(d_i\) 的时候还要判断一下 \(a^i \equiv b \pmod p\) 是否可行

还有一些细节问题我会放在代码之后解释

参考代码：~~仅供参考~~

// inv(i) i \equiv 1 mod p// i * inv(i) + kp = 1 (kown i, p, 1)templateT inv(T i, T p) {    T iv, k;    exgcd(i, p, &iv, &k);    iv %= p;    // 注意点4    return iv < 0 ? iv + p : iv;}data exBSGS(data a, data b, data p) {    // 注意点 1     b %= p;    // 注意点 2    if (b == 1 || p == 1) return 0;    data d, ak(1), k(0);    while ((d = gcd(a, p)) != 1) {        if (b % d) return -1;        ++k, p /= d, b /= d;        ak = a / d * ak % p;        // 注意点 3        if (ak == b) return k;    }    // 注意点 4    b = b * inv(ak, p) % p;    data res = BSGS(a, b, p);    // 注意点 5    if (~res) return res + k;    return -1;}

注意点1：为什么需要一次 b %= p
考虑这样一组数据 a = 10, b = 110, p = 100
其实这个地方也可以加一句 a %= p，可以减少部分运算，也不会影响正确性，反正都是乘法~~，模意义下人人平等~~

注意点2：这里的特判是什么意思
如果p为1，相当于同余式恒成立，所以直接返回最小答案即可
如果b为1，考虑到 \(\forall a \ne 0, a^0 = 1\)，所以直接返回最小答案即可

注意点3：这就是上文中答案小于 \(k\) 情况的特判

注意点4：
由于是在模 \(\frac pD\) 意义下，所以需要通过逆元的方式调整
但是考虑到两者不知道是否互质，所以通过扩展欧几里得算法就行了
扩展欧几里得算法可以参考：算法学习笔记(1): 欧几里得算法及其扩展

注意点5：
由于我们在求 \(D\) 的时候消耗了 \(k\) 个\(a\)，所以需要加上 \(k\) 才是正确答案

关键词：也就是说时间复杂度欧几里得算法