Pohlig-Hellman Algorithm
Pohlig-Hellman decomposes a discrete logarithm in a group of smooth order into discrete logarithms in each prime-power-order subgroup, then merges them with the CRT.
Purpose
To accelerate discrete logarithms in smooth-order groups and guide secure group parameter selection.
Mechanism
If the group order is n=∏p_i^e_i, solve x mod p_i^e_i separately (with BSGS in the subgroup of order p_i^e_i), then merge with the CRT. Hence DH parameters should have an order containing a large prime factor.
Use cases
- Discrete logarithm acceleration
- DH parameter security
- Cryptanalysis