核心概述
离散对数（Discrete Log）：求解 a^x ≡ b (mod m) 的最小非负整数解 x；常用 Baby-Step Giant-Step（BSGS）算法，时间与空间均为 O(√m)。当 gcd(a,m)≠1 时用扩展 BSGS（exBSGS）分解公因子后再求。
原文引述
Description: Solves a^x ≡ b (mod m). Uses baby-step giant-step in O(√m) time and memory when gcd(a,m)=1, and an extended variant that handles non-coprime cases by factoring out gcds first. Time: O(√m) time, O(√m) memory Status: tested
展开阐述
-
函数/接口（据实现）
- discreteLog(a, b, m) → x 或 -1：返回最小非负解 x；若无解返回 -1。
- 可选：当 m 为素数且已知 a 的阶分解时，可用 Pohlig–Hellman 进一步加速（本条仅说明，模板通常提供 BSGS/exBSGS）。
-
核心算法A（BSGS，要求 gcd(a,m)=1）
-
核心算法B（exBSGS，处理 gcd(a,m)≠1）
- 设 k=0，acc=1。
- 循环 g=gcd(a,m)：
- 若 b%g≠0，返回 -1（无解）。
- 否则 m←m/g，b←b/g，acc←acc·(a/g) mod m，k++。
- 若 acc≡b (mod m)，返回 k（此时 x=k 即解）。
- 继续直到 gcd(a,m)=1。
- 令 b’ = b · inv(acc) mod m（消去前缀），在模 m 下对 a、b’ 用 BSGS 求到的解 x’，返回 x = x’ + k。
- 该过程相当于逐步把方程“拉入”可逆域，再在剩余模数上用 BSGS。
-
边界与特判
- b ≡ 1 (mod m) ⇒ x=0 为一解。
- m=1 ⇒ 仅 0≡0 成立，按实现约定返回 0 或 -1。
- a≡0 (mod m)：仅当 b≡0 (mod m) 且 x≥1 有解；取最小者 x=1。
- 需注意取模规范化：统一 0≤a,b<m。
-
输出语义
- 返回最小非负解 x；若不存在解返回 -1。
- 对于存在多解的情况（如在某些非简化模数下），此返回约定仍取最小非负者。
-
复杂度
- 时间 O(√m)，空间 O(√m)；exBSGS 的前置 gcd/逆元/规模缩减为 O(log m)。
-
使用与注意
- 需要可靠的模逆与快速幂：见088-数论-模逆、091-数论-模幂。
- 乘法可能溢出：大模时使用 128 位或见090-数论-长整型模乘。
- 若 m 为素数且 a 的阶 | (m−1)，可用 Pohlig–Hellman 按阶分解在子问题上用 BSGS 并用 081-数论-中国剩余定理 合并（模板未必内置，仅作提示）。
- 哈希表存 baby steps 时注意去重与取最小 j。