一、为什么学离散对数？
Mermaid · 渲染中（下方为源码）
graph TD A[a^x ≡ b mod p] --> B[x = im - j] B --> C[大步查表 + 小步匹配] C --> D[O(√p) BSGS]
解 a^x ≡ b (mod p) 求最小非负整数 x。应用：
- 密码学（Diffie–Hellman、ElGamal）
- 指数循环节化简
- 与原根配合：把乘法群映射成下标运算
二、大步小步法（BSGS）
令 m = ⌈√p⌉，x = i·m − j（0≤i,j<m）：
a^(i·m) ≡ b·a^j (mod p)，两边查哈希表相遇即得解。
int bsgs(int a, int b, int p) {
a %= p; b %= p;
if (b == 1) return 0;
int m = (int) Math.sqrt(p) + 1;
HashMap<Integer, Integer> table = new HashMap<>();
long e = 1;
for (int j = 0; j < m; j++) {
table.put((int) e, j);
e = e * a % p;
}
long am = pow(a, m, p);
long cur = b;
for (int i = 0; i <= m; i++) {
if (table.containsKey((int) cur)) {
int j = table.get((int) cur);
int x = i * m - j;
if (x >= 0) return x;
}
cur = cur * am % p;
}
return -1; // 无解
}