离散对数初步
问题描述
求解 $0\leqslant X < C$ 使得 $\displaystyle X^A \equiv B\hskip -1em \mod C$ 成立。
其中，$C$ 为素数。
问题简析
由于 $C$ 是素数，所以必有 原根 $g$。
用 Baby Step Gaint Step 算法先求出 $\displaystyle g^t \equiv B\hskip -1em\mod C$ 的解 $t$。
令 $\displaystyle X=g^s$，由于 $\displaystyle g^{s\cdot A}=(g^s)^A=X^A\equiv B\hskip -1em\mod C\equiv g^t\hskip -1em\mod C$，
根据 ***数论欧拉定理***，有 $\displaystyle g^{\varphi(C)}\equiv 1\hskip -1em\mod C$；
所以可以用 扩展欧几里得算法 求出 $\displaystyle s\cdot A\equiv t\hskip -1em\mod \varphi(C)$ 的通解 $\displaystyle s=s_0+k\cdot\frac{\varphi(C)}{\gcd\big(\varphi(C),A\big)}$。
再由快速幂求出 $\displaystyle X=g^s=g^{s_0+k\cdot\frac{\varphi(C)}{\gcd\big(\varphi(C),A\big)}}$。
至此，问题圆满解决。
复杂度分析
Baby Step Gaint Step 算法的复杂度是 $O(\sqrt{C})$ 的，一共执行一次；
扩展欧几里得算法是 $O(\log C)$ 的，一共执行一次；
快速幂是 $O(\log C)$ 的，一共要执行 $\displaystyle \gcd\big(\varphi(C),A\big)$ 次，
所以时间复杂度为 $O(\sqrt{C}+\log C+\gcd\big(\varphi(C),A\big)\cdot \log C)$。
空间复杂度与 Baby Step Gaint Step 空间复杂度同阶。
问题扩展
$C$ 是合数呢？
离散对数进阶
问题描述
求解 $0\leqslant X < C$ 使得 $\displaystyle X^A \equiv B\hskip -1em \mod C$ 成立。
其中，$C$ 为素数，不保证 $\gcd(X,C) = 1$。
问题简析
不妨假设 $\displaystyle C=p_1^{k_1}p_2^{k_2}\cdots p_s^{k_s}$。
令 $C_i=p_i^{k_i},~1\leqslant i\leqslant s$。
先考虑如何求 $\displaystyle X_i^A\equiv B\hskip -1em\mod C_i$ 的解。
先考虑 $C_i\mid B$ 的情况
因为 $C_i\mid X_i^A$ 的充要条件为：$X_i^A=p_i^{k_i+\theta}$ 且 $0\leqslant \theta$；或 $X_i=0$。
所以，通解为：$\displaystyle X_i=p_i^{\left\lceil \frac{p_i}{A} \right\rceil+\theta}$ 且 $0\leqslant \theta$；或 $X_i=0$。
再考虑 $C_i\nmid B$ 的情况
- 若 $2 \mid C_i$：
由于 $C_i=2^{k_i}$ 当 $k_i\geqslant 3$ 时不存原根，所以离散对数的方法失效；
由于本人能力有限，未能提供好的方法，目前只能暴力；
如有能力做到 $O(\sqrt{C_i})$ 以下复杂度的朋友，还望不吝赐教。 - 若 $2 \nmid C_i$：
由于 $C_i=p_i^{k_i}$，所以必有原根 $g_i$；
再由 扩展 Baby Step Gaint Step 算法解方程 $\displaystyle g_i^{t_i}\equiv B\hskip -1em\mod C_i$；
剩下的问题可以套用 离散对数初步 解决。
回到原问题
【定理 1】 若 $\displaystyle X^A\equiv B\hskip -1em\mod C$ 成立，则 $\displaystyle (X+C)^A\equiv B\hskip -1em\mod C$ 成立。
由二项式展开即可得证，证明略。
所以，接下来，我们仅需解方程组：
\begin{align}
X &\equiv X_1\hskip -1em\mod C_1 \
X &\equiv X_2\hskip -1em\mod C_2 \
&\cdots \
X &\equiv X_s\hskip -1em\mod C_s
\end{align}
由于 $C_i,C_j$ 两两互质，可由 中国剩余定理 求出 $X$。
至此，问题还算圆满解决。
练习
| problems | categories | solution |
|---|---|---|
| 51Nod/X^A Mod P | 离散对数初步 | Code |
| 51Nod/X^A Mod B | 离散对数进阶 | Code |
Hint
鉴于本人能力有限，有误之处还望指正。
