离散对数问题

给定 \(a, b\) 以及素数 \(p\)，求最小的 \(x\)，使得 \(a^x \equiv b \pmod p\)。

大步小步 (BSGS) 算法

设 \(x = ti - j\)，其中 \(t = \lceil \sqrt p\rceil, 0 \le j < t\)，则方程被转化为： \[ \begin{aligned} a^{ti - j} &\equiv b &\pmod p \\ (a^t)^i &\equiv ba^j &\pmod p \end{aligned} \] 我们首先对于所有的 \(0 \le j < t\) 的 \(ba^j \bmod p\) 插入一个哈希表。接下来我们枚举 \(i\) 的所有取值 \(0, 1, 2, \cdots ,t\)，计算 \((a^t)^i \bmod p\)，查询哈希表中是否存在相应的 \(j\) 即可，复杂度变为 \(O(\sqrt p)\)。

板子

其实哈希表换成 std::map 也行，但是常数会大很多（手写一个哈希表又不是特别麻烦）：

const int HASH = 1000007;
const int ELEM = 6000000;
typedef long long ll;
int tot, fst[HASH], nxt[ELEM];
ll key[ELEM], val[ELEM];

inline void put(ll k, ll v) {
    key[++tot] = k;
    val[tot] = v;
    k %= HASH;
    nxt[tot] = fst[k];
    fst[k] = tot;
}

inline ll lookup(ll k) {
    for (int i = fst[k % HASH]; i; i = nxt[i])
        if (key[i] == k) return val[i];
    return -1;
}

ll bsgs(ll a, ll b, ll p) {
    memset(fst, 0, sizeof(fst));
    tot = 0;
    int t = ceil(sqrt(p));
    ll tmp = b;
    for (int j = 0; j < t; j++, tmp = tmp * a % p) // 计算 b*a^j
        put(tmp, j);
    a = qpow(a, t, p); // a^t
    if (a == 0) return b == 0 ? 1 : -1; // 特判
    tmp = 1;
    for (int i = 0; i <= t; i++, tmp = tmp * a % p) { // 计算 (a^t)^i
        ll j = lookup(tmp);
        if (j >= 0 && i * t - j >= 0) return i * t - j;
    }
    return -1;
}