Ingroup theory, thePohlig–Hellman algorithm, sometimes credited as theSilver–Pohlig–Hellman algorithm,^[1] is a special-purposealgorithm for computingdiscrete logarithms in afinite abelian group whose order is asmooth integer.

The algorithm was introduced by Roland Silver, but first published byStephen Pohlig andMartin Hellman, who credit Silver with its earlier independent but unpublished discovery. Pohlig and Hellman also list Richard Schroeppel and H. Block as having found the same algorithm, later than Silver, but again without publishing it.^[2]

As an important special case, which is used as a subroutine in the general algorithm (see below), the Pohlig–Hellman algorithm applies togroups whose order is aprime power. The basic idea of this algorithm is to iteratively compute the${\displaystyle p}$-adic digits of the logarithm by repeatedly "shifting out" all but one unknown digit in the exponent, and computing that digit by elementary methods.

(Note that for readability, the algorithm is stated for cyclic groups — in general,${\displaystyle G}$ must be replaced by the subgroup${\displaystyle ⟨g⟩}$ generated by${\displaystyle g}$, which is always cyclic.)

Input. A cyclic group${\displaystyle G}$ of order${\displaystyle n=p^e}$ with generator${\displaystyle g}$ and an element${\displaystyle h\in G}$.

Output. The unique integer${\displaystyle x\in \{0,\dots ,n-1\}}$ such that${\displaystyle g^x=h}$.

1. Initialize${\displaystyle x_0:=0.}$
2. Compute${\displaystyle \gamma :=g^{p^{e-1}}}$. ByLagrange's theorem, this element has order${\displaystyle p}$.
3. For all${\displaystyle k\in \{0,\dots ,e-1\}}$, do:
   1. Compute${\displaystyle h_k:=(g^{-x_k}h{)}^{p^{e-1-k}}}$. By construction, the order of this element must divide${\displaystyle p}$, hence${\displaystyle h_k\in ⟨\gamma ⟩}$.
   2. Using thebaby-step giant-step algorithm, compute${\displaystyle d_k\in \{0,\dots ,p-1\}}$ such that${\displaystyle {\gamma }^{d_k}=h_k}$. It takes time${\displaystyle O(\sqrt{p})}$.
   3. Set${\displaystyle x_{k+1}:=x_k+p^k{d}_k}$.
4. Return${\displaystyle x_e}$.

The algorithm computes discrete logarithms in time complexity${\displaystyle O(e\sqrt{p})}$, far better than thebaby-step giant-step algorithm's${\displaystyle O(\sqrt{p^e})}$ when${\displaystyle e}$ is large.

In this section, we present the general case of the Pohlig–Hellman algorithm. The core ingredients are the algorithm from the previous section (to compute a logarithm modulo each prime power in the group order) and theChinese remainder theorem (to combine these to a logarithm in the full group).

(Again, we assume the group to be cyclic, with the understanding that a non-cyclic group must be replaced by the subgroup generated by the logarithm's base element.)

Input. A cyclic group${\displaystyle G}$ of order${\displaystyle n}$ with generator${\displaystyle g}$, an element${\displaystyle h\in G}$, and a prime factorization$n=\prod _{i=1}^r{p}_i^{e_i}$.

Output. The unique integer${\displaystyle x\in \{0,\dots ,n-1\}}$ such that${\displaystyle g^x=h}$.

1. For each${\displaystyle i\in \{1,\dots ,r\}}$, do:
   1. Compute${\displaystyle g_i:=g^{n/p_i^{e_i}}}$. ByLagrange's theorem, this element has order${\displaystyle p_i^{e_i}}$.
   2. Compute${\displaystyle h_i:=h^{n/p_i^{e_i}}}$. By construction,${\displaystyle h_i\in ⟨g_i⟩}$.
   3. Using the algorithm above in the group${\displaystyle ⟨g_i⟩}$, compute${\displaystyle x_i\in \{0,\dots ,p_i^{e_i}-1\}}$ such that${\displaystyle g_i^{x_i}=h_i}$.
2. Solve the simultaneous congruence$${\displaystyle x\equiv x_i(\mathrm{mod}{p}_i^{e_i})\mathrm{\forall }i\in \{1,\dots ,r\}\text{.}}$$TheChinese remainder theorem guarantees there exists a unique solution${\displaystyle x\in \{0,\dots ,n-1\}}$.
3. Return${\displaystyle x}$.

The correctness of this algorithm can be verified via theclassification of finite abelian groups: Raising${\displaystyle g}$ and${\displaystyle h}$ to the power of${\displaystyle n/p_i^{e_i}}$ can be understood as the projection to the factor group of order${\displaystyle p_i^{e_i}}$.

The worst-case input for the Pohlig–Hellman algorithm is a group of prime order: In that case, it degrades to thebaby-step giant-step algorithm, hence the worst-case time complexity is${\displaystyle \mathcal{O}(\sqrt{n})}$. However, it is much more efficient if the order is smooth: Specifically, if${\displaystyle \prod _i{p}_i^{e_i}}$ is the prime factorization of${\displaystyle n}$, then the algorithm's complexity is$${\displaystyle \mathcal{O}\left(\sum _i{e}_i(\log n+\sqrt{p_i})\right)}$$ group operations.^[3]

• Mollin, Richard (2006-09-18).An Introduction To Cryptography (2nd ed.). Chapman and Hall/CRC. p. 344.ISBN 978-1-58488-618-1.
• Pohlig, S.;Hellman, M. (1978)."An Improved Algorithm for Computing Logarithms over GF(p) and its Cryptographic Significance"(PDF).IEEE Transactions on Information Theory (24):106–110.doi:10.1109/TIT.1978.1055817.
• Menezes, Alfred J.;van Oorschot, Paul C.;Vanstone, Scott A. (1997)."Number-Theoretic Reference Problems"(PDF).Handbook of Applied Cryptography.CRC Press. pp. 107–109.ISBN 0-8493-8523-7.

• Number theoretic algorithms

• Articles with short description
• Short description is different from Wikidata