POJ 2417 / BZOJ 3239 Discrete Logging：BSGS 算法求離散對數

問題描述

給定質數 P (2 ≤ P < 2^31)，基數 B (2 ≤ B < P)，目標 N (1 ≤ N < P)，求最小非負整數 L 使得 B^L ≡ N (mod P)。無解輸出 "no solution"。

Baby-Step Giant-Step (BSGS) 算法

設 L = i*m - j，其中 m = ceil(sqrt(P))。則 B^{i*m} ≡ N * B^j (mod P)。
預計算所有 B^j (j=0..m-1) 存入哈希表。
然後枚舉 i=0..m，計算 B^{i*m}，查找是否存在匹配的 N * B^j。
找到則 L = i*m - j，取最小非負解。

處理非互質情況 (擴展 BSGS)

若 B 和 P 不互質（P 為質數故 B

複雜度

• 時間：O(√P log √P) ≈ O(√P)。
• 空間：O(√P)。

參考程式碼 (C++)

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;

int64 mod_mul(int64 a, int64 b, int64 mod) {
    return (__int128)a * b % mod;
}

int64 mod_pow(int64 a, int64 e, int64 mod) {
    int64 r = 1;
    while (e) {
        if (e & 1) r = mod_mul(r, a, mod);
        a = mod_mul(a, a, mod);
        e >>= 1;
    }
    return r;
}

int64 bsgs(int64 a, int64 b, int64 p) { // a^x = b (mod p), p prime
    a %= p; b %= p;
    if (b == 1) return 0;
    int64 m = (int64)sqrt(p) + 1;
    unordered_map mp;
    int64 cur = b;
    for (int64 j = 0; j < m; ++j) {
        if (!mp.count(cur)) mp[cur] = j;
        cur = mod_mul(cur, a, p);
    }
    int64 am = mod_pow(a, m, p);
    cur = 1;
    for (int64 i = 1; i <= m; ++i) {
        cur = mod_mul(cur, am, p);
        if (mp.count(cur)) {
            int64 ans = i * m - mp[cur];
            if (ans < p) return ans;
        }
    }
    return -1;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int64 P, B, N;
    while (cin >> P >> B >> N) {
        int64 ans = bsgs(B, N, P);
        if (ans == -1) cout << "no solution\n";
        else cout << ans << '\n';
    }
    return 0;
}