Pohlig-Hellman Algorithm

Purpose: Solve the discrete logarithm $g^x\equiv h(\mathrm{mod}p)$ in $O\left({\sum }_i{e}_i(\log n+\sqrt{p_i})\right)$ when the group order $n$ factors into small primes $n=\prod p_i^{e_i}$. It is what makes “smooth-order” groups cryptographically worthless.

Algorithm

Let $n=\mathrm{ord}(g)={\prod }_i{p}_i^{e_i}$.

1. For each prime power $p_i^{e_i}$:
   • Reduce to a subgroup of order $p_i^{e_i}$ by raising to the power $n/p_i^{e_i}$:
     $g_i=g^{n/p_i^{e_i}},h_i=h^{n/p_i^{e_i}}.$
   • Solve $g_i^{x_i}=h_i$ digit by digit in base $p_i$: write $x_i=c_0+c_1{p}_i+\cdots +c_{e_i-1}{p}_i^{e_i-1}$ and recover each $c_j$ with one discrete log in the subgroup of order $p_i$ (via baby-step giant-step or Pollard’s kangaroo, $O(\sqrt{p_i})$).
2. Combine the residues $x\equiv x_i(\mathrm{mod}{p}_i^{e_i})$ with the Chinese Remainder Theorem.

Complexity

$O\left({\sum }_i{e}_i(\log n+\sqrt{p_i})\right)$

• If every $p_i$ is small (the group order is smooth), this is essentially polynomial — the discrete log is easy.
• If $n$ has one huge prime factor, Pohlig-Hellman degenerates to $O(\sqrt{p_{\max }})$, i.e. no better than generic square-root attacks.

Why It Works

The group ${\mathbb{Z}}_n$ of exponents decomposes by CRT as $\prod {\mathbb{Z}}_{p_i^{e_i}}$. Raising to $n/p_i^{e_i}$ projects onto the $i$-th factor, killing every other component. Within a $p_i$-power subgroup, the base-$p_i$ digit extraction works because raising to $p_i^{e_i-1}$ isolates the least significant digit, then that digit is stripped off and the process repeats. CRT reassembles the pieces. ∎

Security implication

This is the reason cryptographic groups are always chosen with $|G|=2q$ or $|G|=q$ for a large prime $q$. A “safe prime” $p=2q+1$ is safe precisely because $p-1=2q$ is not smooth. Pohlig-Hellman is the concrete attack that rules out everything else.

Comparison of discrete log methods

Method	Time	Needs
Brute force	$O(n)$	nothing
Baby-step giant-step	$O(\sqrt{n})$ time and space	nothing
Pollard’s kangaroo / rho	$O(\sqrt{n})$ time, $O(1)$ space	nothing
Pohlig-Hellman	$O(\sum e_i\sqrt{p_i})$	smooth group order
Index calculus	sub-exponential	${\mathbb{F}}_p^{\ast }$ specifically (not elliptic curves)

Variants / Use Cases

• Discrete Logarithm — the topic page, with baby-step giant-step code
• Primitive roots — finding one requires the factorisation of $p-1$, the same input Pohlig-Hellman needs
• Discrete root — solving $x^k\equiv a$ reduces to a discrete log plus a linear congruence
• Elliptic curve cryptography — the same attack applies to the curve group order, which is why curve orders are published with their factorisation