DLP中常用算法

Pohlig-Hellman 算法（光滑阶）

给定 a,b,p，p 是素数，求 x，$a^x\equiv b(modp)$ 在模 p 下，设该群的生成元为 g，则有

$$\begin{gathered} a\equiv g^{a1}(modp) \\ b\equiv g^{b1}(modp) \end{gathered}$$

联立条件有

$$g^{a1x}\equiv g^{b1}(modp)$$

由欧拉定理得$\varphi (p)=p-1$，则有$a1x=b1(mod(p-1))$

1.将 p-1 分解，即 $p-1=p_1^{k_1}{p}_2^{k_2}\cdots p_m^{k_m}$

2.将 x 表示成$p_i$ 进制, 列出方程 $$x=p_i^0{a}_0+p_i^1{a}_1+...+p_i^{k_i-1}a\ast k_i-1$$

3.令 r=1，求$(a^x{)}^{\frac{p-1}{p_i^r}}\equiv b^{\frac{p-1}{p_i^r}}(modp)$

4.将 2 中的公式代入到 3，展开得到 $$a^{a0\ast \frac{p-1}{p_i}}\ast a^{(p-1)a1}\ast a^{(p-1)p_i{a}_2}...a^{(p-1)p_i^{k_i-2}{a}_{k_i-1}}\equiv b^{\frac{p-1}{p_i}}(modp)$$

5.从第二项开始，后面每项都是 1，欧拉定理:$a^{(p-1)}\equiv 1(modp)$，化简得到的式子为 $${a}^{a0\ast \frac{p-1}{p_i}}\equiv b^{\frac{p-1}{p_i}}(modp)$$ 因为该方程只有 a0 未知，所以可在[0,pi-1]范围内爆破出 a0

6.再令 r = 2,3,4...ki，重复步骤 3，即可求出所有的$a_2,a_3....a_{k_i-1}$，从而得到 m 个关于 x 的方程，最后使用 CRT 进行求解即可。

总结:将 p-1 的 m 个质因子，分别求出其方程内的所有系数 a，从而构造了 m 个关于 x 的方程，最终利用 CRT 求解。