[Solution && Learning Record] exBSGS

· · 题解

\text{BSGS} 算法

概念

BSGS 算法用于求解离散对数同余方程

a^t\equiv b\pmod{p}

算法

我们先讨论 a 和 p 互质的情况。

首先由欧拉定理可以知道

a^{t}\equiv a^{t\mod{\varphi(p)}}\pmod{p}

而又知 \varphi(p)<p ，那么考虑暴力枚举 1\sim p，一定可以找出最小的非负整数 t

设 k=\sqrt{p}+1 ，t=kx-y ，其中

\begin{aligned} x\in[1,\ k],\quad y\in[0,\ k-1] \end{aligned}

这样通过枚举 x,y ，一定可以遍历到 1\sim p 。当然开始时要对 x=0 进行特判。

发现 x,y\sim \Theta(\sqrt{p}) 。那么考虑优化：首先将问题转化为求解

a^{kx}\equiv b\cdot a^y\pmod{p}

用一个 Hash 表将右边所有的取值与 y 的对应存下来，然后枚举 x ，在 Hash 表中查找是否有与 a^{kx} 对应的 y 即可。预处理和枚举的时间复杂度都是 \Theta(\sqrt{p}) 级别，因此总复杂度就是 \Theta(\sqrt{p}) 。

Q & A

Q : 为什么 x 一定要从 1 开始枚举？

A : 考虑 x=0 的情况，如果继续上面的枚举，那么相当于求 1\equiv ba^y\pmod{p} ，这样的 y 一定是负数，而 BSGS 求解的 t 经常要求是非负整数。所以从 1 开始枚举。

exBSGS

此时不要求 a,p 互质，那么怎么求解呢？

注意到

a^t\equiv b\pmod{p} \Leftrightarrow a^t+kp=b

令 d=\gcd(a,p) ，等式的左边显然能被 d 整除，那么可分为两种情况

  2. $$ \begin{aligned} &\dfrac{a}{d}a^{t-1}+k\dfrac{p}{d}=\dfrac{b}{d}\\ \Leftrightarrow & \dfrac{a}{d}a^{t-1}\equiv \dfrac{b}{d}\pmod{\dfrac{p}{d}}\\ \Leftrightarrow & a^{t-1}\equiv \dfrac{b}{d}\cdot\left(\dfrac{a}{d}\right)^{-1}\pmod{\dfrac{p}{d}}\\ \end{aligned} $$

如果 a 和 \dfrac{p}{d} 已经互质了，那么直接用 BSGS 求解即可，如果不互质，递归执行步骤。事实上，由于因数有限，递归次数一定不会超过 \mathcal{O}(\log p)

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <unordered_map>

using namespace std;

typedef long long LL;

const int INF = 0x3f3f3f3f;

int a, b, p;
unordered_map<int, int> hs;

int exgcd(int a, int b, int &x, int &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

int BSGS(int a, int b, int p) {
    if (1 % p == b % p) return 0;
    int k = sqrt(p) + 1;
    hs.clear();
    for (int y = 0, r = b % p; y < k; y++) {
        hs[r] = y;
        r = (LL)r * a % p;
    }
    int ak = 1;
    for (int i = 1; i <= k; i++) ak = (LL)ak * a % p;
    for (int x = 1, l = ak; x <= k; x++) {
        if (hs.count(l)) return k * x - hs[l];
        l = (LL)l * ak % p;
    }
    return -INF;
}

int exBSGS(int a, int b, int p) {
    b = (b % p + p) % p;
    if (1 % p == b % p) return 0;
    int x, y;
    int d = exgcd(a, p, x, y);
    if (d > 1) {
        if (b % d) return -INF;
        exgcd(a / d, p / d, x, y);
        return exBSGS(a, (LL)b / d * x % (p / d), p / d) + 1;
    }
    return BSGS(a, b, p);
}

int main() {
    while (~scanf("%d%d%d", &a, &p, &b), a || b || p) {
        int res = exBSGS(a, b, p);
        if (res < 0) puts("No Solution");
        else printf("%d\n", res);
    }
    return 0;
}