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

題目大意

給質數 P (≤ 2³¹), 基數 B (2 ≤ B < P), 目標 N (1 ≤ N < P)。求最小非負整數 L 使 `B^L ≡ N (mod P)`。無解輸出 "no solution"。多測試案例。

算法：Baby-Step Giant-Step (BSGS)

• 設 `m = ceil(sqrt(P))`。寫 `L = i·m - j` (0 ≤ i,j < m)。
• 方程變為 `B^{i·m} ≡ N·B^j (mod P)`。
• 預計算所有 `j`：`value = N * B^j mod P`，存入哈希表 `value → j`（保留最小 j）。
• 枚舉 `i = 0..m`：計算 `cur = B^{i·m} mod P`，查哈希表是否存在 `cur`。若存在，`L = i·m - j` 為候選解，取最小值。
• 注意 `B` 與 `P` 不互質時需特殊處理，但題目 P 為質數，B < P，故互質。

代碼關鍵片段

const int MOD = 76543; // 哈希表大小，取質數
int head[MOD], nxt[MAXM], val[MAXM], id[MAXM], ecnt;

void hashInsert(int v, int i) {
    int k = v % MOD;
    val[ecnt] = v; id[ecnt] = i; nxt[ecnt] = head[k]; head[k] = ecnt++;
}
int hashFind(int v) {
    int k = v % MOD;
    for (int i = head[k]; ~i; i = nxt[i])
        if (val[i] == v) return id[i];
    return -1;
}

int BSGS(int a, int b, int p) { // a^L ≡ b (mod p)
    if (b == 1) return 0;
    memset(head, -1, sizeof(head));
    ecnt = 0;
    int m = (int)sqrt(p) + 1;
    long long v = b;
    for (int j = 0; j < m; ++j) {
        if (hashFind(v) == -1) hashInsert(v, j); // 保留最小 j
        v = v * a % p;
    }
    long long factor = 1;
    for (int i = 0; i < m; ++i) factor = factor * a % p; // a^m
    long long cur = 1;
    for (int i = 0; i <= m; ++i) {
        int j = hashFind(cur);
        if (j != -1) {
            long long L = 1LL * i * m - j;
            if (L >= 0) return (int)L;
        }
        cur = cur * factor % p;
    }
    return -1;
}

複雜度

• 時間：O(√P) ≈ 46340 步，極快。
• 空間：O(√P) 哈希表。

關鍵點

• **哈希表去重**：同一 value 保留最小 j，保證 L 最小。
• **L = i·m - j** 形式避免了負數處理（對比 `L = i·m + j` 需模 P）。
• **大質數模乘** 用 `long long` 防溢出。

總結

POJ 2417 是 BSGS 算法的經典模板題。離散對數問題在密碼學中極其重要，BSGS 將 O(P) 降為 O(√P)。掌握「巨步小步」分解與哈希表查找，是數論算法必修課。