给定 \(a,P\)，\(P\) 是质数，设 \(g\) 为 \(P\) 的原根，求出 \(g^x\equiv a\mod P\)

Pohlig–Hellman algorithm

对 \(P-1\) 唯一分解，设为 \(\prod p_i^{e_i}\)，对每个 \(p_i^{e_i}\) 解出：

那么有 \(x \equiv x_i\mod p_i^{e_i}\)
我们最后只需要解一个同余方程即可，问题转化为对每个 \(p_i^{e_i}\) 求出 \(x_i\)
我们考虑 \(x_i\) 的 \(p_i\) 进制表示，不妨设为 \(b_0+b_1p+\dots +b_{e_i-1}p^{e_i-1}\)
下面的做法将始我们按位确定 \(b_i\)，如何做呢？
我们知道：\((g^{x_i})^{\frac{P-1}{p_i}}\equiv a^{\frac{P-1}{p_i}}\mod P\)
即 \(g^{b_0\frac{p-1}{p_i}+b_1(p-1)+b_2(p-1)p_i+\dots}=a^{\frac{p-1}{p_i}}\mod P\)
注意到后面就都是 \(1\) 了，故 \(g^{b_0\frac{p-1}{p_i}}\equiv a^{\frac{p-1}{p_i}}\mod P\)
此时枚举 \(b_0\) 就可以算出
然后我们再考虑 \((g^{x_i})^{\frac{p-1}{p_i^2}}\equiv a^{\frac{p-1}{p_i^2}}\mod P\)
此时只需要把 \(g^{b_0\frac{p-1}{p_i^2}}\) 除过去就能变成一个子问题
每次需要快速幂和求逆，每一轮枚举可以用 BSGS，故复杂度为 \(\sum e_i(\log P+\sqrt p_i)\)

Pohlig–Hellman algorithm

原文：https://www.cnblogs.com/FSYo/p/14882380.html