DLP中常用算法

Pohlig-Hellman 算法（光滑阶）

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

\[ a \equiv g^{a1} (mod\;p) \newline b \equiv g^{b1} (mod\;p) \]

联立条件有

\[ g^{a1x} \equiv g^{b1} (mod\;p) \]

由欧拉定理得\(\phi(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^0a_0 + p_i^1a_1+...+p_i^{k_i-1}a*{k_i-1}\]

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

4.将 2 中的公式代入到 3，展开得到 \[a^{a0*\frac{p-1}{p_i}}* a^{(p-1)a1} * a^{(p-1)p_ia_2}...a^{(p-1)p_i^{k_i-2}a_{k_i-1}} \equiv b^{\frac{p-1}{p_i}}(mod\;p)\]

5.从第二项开始，后面每项都是 1，欧拉定理:\(a^{(p-1)} \equiv 1(mod\;p)\)，化简得到的式子为 \[\newline a^{a0*\frac{p-1}{p_i}} \equiv b^{\frac{p-1}{p_i}}(mod \;p)\newline\] 因为该方程只有 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 求解。