Pohlig-Hellman 算法
参考：Wikipedia
Pohlig-Hellman 算法是一种在有限交换群中高效实现离散对数的方法。例如，要求解 \(x\) 使得：\(2^x = 22 \pmod{43}\)，如何高效地进行计算？
方法一：枚举 \(x\)，找到满足要求的值为止，可以得到 \(x=13\)。
方法二：用 Baby-step Giant-step 方法。
方法三：使用 Pohlig-Hellman 算法，它的思路是，把问题分解成子群上的问题，例如上述 \(2^x = 22 \pmod {43}\) 可以分解，这个群的阶是 \(42 = 2 * 3 * 7\)，可以拆出来阶为 2、3 和 7 的子群。
具体地说，如果 \(2^x = 22 \pmod {43}\) 成立，那么一定有 \((2^{21})^x = 22^{21} \pmod {43}\)，此时 \(2^{21}\) 的阶是 2，意味着 \(x_1 = x \bmod 2\) 的值决定了这个等式是否成立；类似地，\(x_2 = x \bmod 3\) 的值决定了 \((2^{14})^x = 22^{14} \pmod {43}\) 是否成立，\(x_3 = x \bmod 7\) 的值决定了 \((2^{6}) ^ x = 22^{6} \pmod {43}\) 是否成立。那么 \(x_1, x_2, x_3\) 就可以用前面的方法二来解，把一个阶很大的群中的离散对数问题，变成多个阶比较小的群的离散对数问题。
求解 \((2^{21})^x = 22^{21} \pmod {43}\) 可得 \(x_1 = x \bmod 2 = 1\)，类似可得 \(x_2 = x \bmod 3 = 1, x_3 = x \bmod 7 = 6\)，那么为了求 \(x\)，最后用中国剩余定理即可：\(x = (1*21+1*28+6*36) \bmod 42 = 13\)。