离散对数问题旨在求解满足同余方程 $a^x \equiv b \pmod p$ 的最小非负整数 $x$。当 $a$ 与 $p$ 互质时，大步小步算法（Baby-step Giant-step，简称 BSGS）能够在 $\Theta(\sqrt{p})$ 的时间复杂度内解决该问题。

根据欧拉定理，若 $\gcd(a, p) = 1$，则 $a^{\varphi(p)} \equiv 1 \pmod p$。这意味着指数 $x$ 具有周期性，解必然存在于 $0$ 到 $\varphi(p)$ 的范围内。为了优化暴力枚举，我们将 $x$ 表示为 $i \times m - j$ 的形式，其中 $m = \lceil \sqrt{p} \rceil$，$i \in [1, m]$，$j \in [0, m-1]$。

代入原方程可得：

$$a^{i \times m - j} \equiv b \pmod p$$

移项处理后得到：

$$a^{i \times m} \equiv b \times a^j \pmod p$$

采用减法形式 $i \times m - j$ 的核心优势在于避免了模逆元的计算。算法流程分为两个阶段：

1. 小步（Baby Step）： 枚举 $j$，计算 $b \times a^j \pmod p$ 并将结果存入哈希表，记录对应的 $j$ 值。
2. 大步（Giant Step）： 枚举 $i$，计算 $a^{i \times m} \pmod p$，并在哈希表中查找是否存在匹配值。若找到，则 $x = i \times m - j$ 即为解。

需要注意的是，若 $a \equiv 0 \pmod p$ 且 $b \not\equiv 0 \pmod p$，方程无解。

整数域实现

以下是基于上述原理的 C++ 实现。代码使用了快速幂算法来计算模幂，并利用 map 存储中间结果。

#include <iostream>
#include <map>
#include <cmath>
#include <algorithm>

using namespace std;
typedef long long ll;

const ll NOT_FOUND = -1;
ll mod_val, base_val, target_val;
ll block_size;
map<ll, ll> table;

ll read_int() {
    ll x = 0, sign = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') sign = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * sign;
}

ll power_mod(ll a, ll b, ll m) {
    ll res = 1;
    a %= m;
    while (b > 0) {
        if (b & 1) res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

void build_table() {
    ll cur = target_val;
    for (ll j = 0; j < block_size; ++j) {
        if (table.find(cur) == table.end()) {
            table[cur] = j;
        }
        cur = cur * base_val % mod_val;
    }
}

ll search_solution() {
    ll step_val = power_mod(base_val, block_size, mod_val);
    ll cur = step_val;
    for (ll i = 1; i <= block_size; ++i) {
        if (table.find(cur) != table.end()) {
            return i * block_size - table[cur];
        }
        cur = cur * step_val % mod_val;
    }
    return NOT_FOUND;
}

int main() {
    mod_val = read_int();
    base_val = read_int();
    target_val = read_int();
    
    block_size = ceil(sqrt(mod_val));
    table.clear();
    
    build_table();
    ll ans = search_solution();
    
    if (ans == NOT_FOUND) {
        printf("no solution\n");
    } else {
        printf("%lld\n", ans);
    }
    return 0;
}

矩阵形式的扩展

BSGS 算法同样适用于矩阵离散对数问题，即求解 $A^x \equiv B \pmod p$，其中 $A, B$ 为方阵。由于矩阵乘法满足结合律且上述算法推导过程中未涉及除法运算，因此可以直接套用该框架。为了在哈希表中存储矩阵，需要设计合适的哈希函数将矩阵映射为整数值。

#include <iostream>
#include <map>
#include <cmath>
#include <cstring>

using namespace std;
typedef long long ll;

const ll INF = 1e18;
const unsigned int SEED1 = 13331;
const unsigned int SEED2 = 131;

int n;
ll mod_val;
ll block_size;
ll ans = INF;

struct Matrix {
    ll data[105][105];
    unsigned int h1, h2;

    void clear() {
        memset(data, 0, sizeof(data));
        h1 = h2 = 0;
    }

    void update_hash() {
        h1 = 0; h2 = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                h1 = h1 * SEED1 + (unsigned int)data[i][j];
                h2 = h2 * SEED2 + (unsigned int)data[i][j];
            }
        }
    }

    Matrix operator*(const Matrix &other) const {
        Matrix res; res.clear();
        for (int i = 1; i <= n; ++i) {
            for (int k = 1; k <= n; ++k) {
                if (data[i][k] == 0) continue;
                for (int j = 1; j <= n; ++j) {
                    res.data[i][j] = (res.data[i][j] + data[i][k] * other.data[k][j]) % mod_val;
                }
            }
        }
        res.update_hash();
        return res;
    }
};

map<pair<unsigned int, unsigned int>, int> table;

ll read_int() {
    ll x = 0, sign = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') sign = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * sign;
}

Matrix power_mod(Matrix a, ll b) {
    Matrix res; res.clear();
    for (int i = 1; i <= n; ++i) res.data[i][i] = 1;
    res.update_hash();
    while (b > 0) {
        if (b & 1) res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

void build_table(Matrix A, Matrix B) {
    table.clear();
    Matrix cur = B;
    for (int j = 0; j < block_size; ++j) {
        cur.update_hash();
        pair<unsigned int, unsigned int> key = {cur.h1, cur.h2};
        if (table.find(key) == table.end()) {
            table[key] = j;
        }
        cur = cur * A;
    }
}

void search_solution(Matrix A) {
    ans = INF;
    Matrix step = power_mod(A, block_size);
    Matrix cur = step;
    for (int i = 1; i <= block_size; ++i) {
        cur.update_hash();
        pair<unsigned int, unsigned int> key = {cur.h1, cur.h2};
        if (table.find(key) != table.end()) {
            ans = min(ans, (ll)i * block_size - table[key]);
        }
        cur = cur * step;
    }
}

int main() {
    n = read_int();
    mod_val = read_int();
    block_size = ceil(sqrt(mod_val));

    Matrix A, B;
    A.clear(); B.clear();

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            A.data[i][j] = read_int();
    A.update_hash();

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            B.data[i][j] = read_int();
    B.update_hash();

    build_table(A, B);
    search_solution(A);

    printf("%lld\n", ans);
    return 0;
}