Pohig-Hellman
Pohig-Hellman算法是一种求解光滑阶循环群上的离散对数的方法。
Pohlig-Hellman算法的复杂度在一般情况下比BSGS算法高，但是在特殊情况下（循环群的阶是光滑数，即可以因子分解成较小的数的乘积），使用Pohlig-Hellman能取得好的效果。而且有些时候，尽管BSGS能够将复杂度降至$\sqrt{p}$，但是这个数依然很大，所以不能用。这时可以考虑Pohlig-hellman方法能不能起作用。
算法思想
考虑DLP问题：$a^x \equiv b \pmod p$，因为 $p$ 是大素数，模 $p$ 的循环群的阶是 $p−1$。假设模 $p$ 的最小的原根是 $g$（原根是可以求的），那么有
在数论，特别是整除理论中，原根是一个很重要的概念。
对于两个正整数$gcd(a,m)=1$可知，存在正整数$d\leq m-1$ 比如说$d=\varphi (m)$，即小于等于$m$的正整数中与$m$互素的正整数的个数，使得$a^{d}\equiv 1{\pmod {m}}$。
由此，在$gcd(a,m)=1$时，定义$a$对模$m$的指数${\displaystyle \delta _{m}(a)}$为使$a^{d}\equiv 1{\pmod {m}}$成立的最小的正整数$d$由前知${\displaystyle \delta _{m}(a)}$一定小于等于$\varphi (m)$，若${\displaystyle \delta _{m}(a)=\varphi (m)}$，则称$a$是模$m$的原根。
举个例子：
设$m=7$，则$\varphi (m)$等于6。
- 设$a=2$，由于${\displaystyle 2^{1}\equiv 2{\pmod {7}}}$，${\displaystyle 2^{2}\equiv 4{\pmod {7}}}$，${\displaystyle 2^{3}\equiv 1{\pmod {7}}}$，${\displaystyle 2^{4}\equiv 2{\pmod {7}}}$，${\displaystyle 2^{5}\equiv 4{\pmod {7}}}$，${\displaystyle 2^{6}\equiv 1{\pmod {7}}}$，因此有${\displaystyle Ord_{7}(2)=3\neq \varphi (7)}$，所以 2 不是模 7 的一个原根。
- 设$a=3$，由于$3^{1}\equiv 3{\pmod {7}}$，$3^{2}\equiv 2{\pmod {7}}$，$3^{3}\equiv 6{\pmod {7}}$，$3^{4}\equiv 4{\pmod {7}}$，$3^{5}\equiv 5{\pmod {7}}$，$3^{6}\equiv 1{\pmod {7}}$，$Ord_{7}(3)=6=\varphi (7)$，所以 3 是模 7 的一个原根。
$\left\{\begin{array}{c} a \equiv g^{a’} \pmod p \\ b \equiv g^{b’} \pmod p \end{array}\right.$
进一步有 $a^x \equiv b \pmod p \Longleftrightarrow g^{a’x} \equiv g^{b’} \pmod p$，
有 $a’x \equiv b’ \pmod {p-1}$，（$g^{a’x} \equiv g^{b’} \pmod p\Longleftrightarrow g^{k(p-1)+[a'x\ mod\ (p-1)]}\equiv g^{k(p-1)+[b'x\ mod\ (p-1)]}\ (mod\ p)$根据费马小定理有$g^{p-1}\equiv 1\ (mod\ p)$，所以可以得到$g^{a'x\ mod\ (p-1)}\equiv g^{b'x\ mod\ (p-1)}\ (mod\ p)$，从而得到$a’x \equiv b’ \pmod {p-1}$）
如果求出了满足上式的 $a’$ 和 $b’$ ，通过扩展gcd方法可以求一次同余方程的解得到 $x$ 。
问题归结成如何求 $a’$ 和 $b’$ ，即原本的一个离散对数问题，现在变成两个离散对数问题：
$\left\{\begin{array}{c} a \equiv g^{a’} \pmod p \\ b \equiv g^{b’} \pmod p \end{array}\right.$
以求 $a’$ 为例，解DLP问题：$g^x \equiv a \pmod p$：
- 将 $p-1$ 进行标准的素因子分解，即 $p-1=\prod\limits_{i=1}^{m} p_i^{k_i}=p_1^{k_1}p_2^{k_2}p_3^{k_3} \cdots p_m^{k_m}$；
- 对每个素因子 $p_i$，将 $x$ 表示成 $p_i$ 进制，有
$x=a_0+a_1p_i+a_2p_i^2+a_3p_i^3+\dots+a_{k_i-1}p_i^{k_i-1} \pmod {p_i^{k_i}}$，
这样的 $p_i$ 进制表示，系数 $a_i$ 自然是小于 $p_i$；
- 令 $r=1$，有 $(g^x)^{\frac{p-1}{p_i^r}} \equiv a^{\frac{p-1}{p_i^r}} \pmod p$，展开 $x$ 有
$(g^{a_0+a_1p_i+a_2p_i^2+a_3p_i^3+\dots+a_{k_i-1}p_i^{k_i-1}})^{\frac{p-1}{p_i^r}} \equiv a^{\frac{p-1}{p_i^r}} \pmod p$
$g^{a_0{\frac{p-1}{p_i}}} \cdot g^{a_1(p-1)} \cdot g^{a_2(p-1)p_i} \cdots g^{a_{k_i-1}(p-1)p_i^{k_i-2}} \equiv a^{\frac{p-1}{p_i}} \pmod p$
注意从第二项开始，每一项指数都包含 $p−1$（由费马小定理知 $g^{p-1} \equiv 1 \pmod p$），所以式子变成
$g^{a_0{\frac{p-1}{p_i}}} \equiv a^{\frac{p-1}{p_i}} \pmod p$
这个式子中只有 $a_0$ 是未知的，因为 $a_0 \in [0,p_i−1]$，所以可以穷举得到 $a_0$ 的值。
- 再令 $r=2,3,4,\cdots,k_i$，重复步骤3，依次穷举求出 $a_1,a_2,\cdots,a_{k_i-1}$，整个的时间复杂度是 $\mathrm{O}(p_ik_i)$。可以得到
$x=a_0+a_1p_i+a_2p_i^2+a_3p_i^3+\dots+a_{k_i-1}p_i^{k_i-1} \pmod {p_i^{k_i}}$
- 重复上述过程，得到 $m$ 个关于 $x$ 的式子，利用中国剩余定理（CRT），可以计算出 $x$ 的值。
利用这个方法求出 $a’$ 和 $b’$ 后，就可以得到原DLP问题的解。
注：
Pohlig-Hellman算法最重要的点是利用了原根的性质，它只能解决 $a \equiv g^x \pmod p$（$g$ 是原根）的问题，对于 $g$ 不是原根的情况，需要利用原根将原方程转化成两个关于原根的离散对数问题。
注意Pohlig-hellman只能用于求解光滑阶群，也就是 $p-1$ 可以分解成小的素因子乘积。否则，穷举 $a_i$ 的时间复杂度依旧很高。另外可以考虑在穷举 $a_i$ 时利用小步大步算法，进一步优划算法复杂度。
