Pohlig–Hellman algorithm

In group theory, the Pohlig–Hellman algorithm, sometimes credited as the Silver–Pohlig–Hellman algorithm, is a special-purpose algorithm for computing discrete logarithms in a finite abelian group whose order is a smooth integer. The algorithm was introduced by Roland Silver, but first published by Stephen Pohlig and Martin 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.

In group theory, the Pohlig–Hellman algorithm, sometimes credited as the Silver–Pohlig–Hellman algorithm, is a special-purpose algorithm for computing discrete logarithms in a finite abelian group whose order is a smooth integer. The algorithm was introduced by Roland Silver, but first published by Stephen Pohlig and Martin 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. Input. A cyclic group G of order n=p^e with generator g and an element h\in G . Output. The unique integer x\in\{0,\dots,n-1\} such that g^x=h . Initialize x_0:=0. Compute \gamma:=g^{p^{e-1}} . By Lagrange's theorem, this element has order p . For all k\in\{0,\dots,e-1\} , do: Compute h_k:=(g^{-x_k}h)^{p^{e-1-k}} . By construction, the order of this element must divide p , hence h_k\in\langle\gamma\rangle . Using the baby-step giant-step algorithm, compute d_k\in\{0,\dots,p-1\} such that \gamma^{d_k}=h_k . It takes time O(\sqrt p) . Set x_{k+1}:=x_k+p^kd_k . Return x_e . The algorithm computes discrete logarithms in time complexity O(e\sqrt p) , far better than the baby-step giant-step algorithm's O(\sqrt{p^e}) when e is large. Input. A cyclic group G of order n with generator g , an element h\in G , and a prime factorization n=\prod_{i=1}^rp_i^{e_i} . Output. The unique integer x\in\{0,\dots,n-1\} such that g^x=h . For each i\in\{1,\dots,r\} , do: Compute g_i:=g^{n/p_i^{e_i}} . By Lagrange's theorem, this element has order p_i^{e_i} . Compute h_i:=h^{n/p_i^{e_i}} . By construction, h_i\in\langle g_i\rangle . Using the algorithm above in the group \langle g_i\rangle , compute x_i\in\{0,\dots,p_i^{e_i}-1\} such that g_i^{x_i}=h_i . Solve the simultaneous congruence x\equiv x_i\pmod{p_i^{e_i}} \quad\forall i\in\{1,\dots,r\} \text{.} The Chinese remainder theorem guarantees there exists a unique solution x\in\{0,\dots,n-1\} . Return x . The correctness of this algorithm can be verified via the classification of finite abelian groups: raising g and h to the power of n/p_i^{e_i} can be understood as the projection to the factor group of order p_i^{e_i} .

Complexity

The worst-case input for the Pohlig–Hellman algorithm is a group of prime order: in that case, it degrades to the baby-step giant-step algorithm, hence the worst-case time complexity is \mathcal O(\sqrt n) . However, it is much more efficient if the order is smooth: Specifically, if \prod_i p_i^{e_i} is the prime factorization of n , then the algorithm's complexity is \mathcal O\left(\sum_i {e_i(\log n+\sqrt {p_i})}\right) group operations.

Notes

References

Text derived from https://en.wikipedia.org/w/index.php?oldid=1367202764 under CC BY-SA 4.0; modifications have been made.