Pohlig-Hellman Algorithm
Pohlig-Hellmanは、滑らかな位数を持つ群の離散対数を、各素数冪位数の部分群の離散対数に分解し、CRTで統合する手法である。
目的
滑らか位数の群で離散対数を高速化し、安全な群パラメータの選択を導く。
メカニズム
群の位数がn=∏p_i^e_iなら、x mod p_i^e_iをそれぞれ別々に解き（位数p_i^e_iの部分群でBSGSを使う）、CRTで統合する。したがってDHパラメータの位数には大きな素因数を含めるべきである。
ユースケース
- 離散対数の高速化（アクセラレーション）
- DHパラメータの安全性
- 暗号解読（クリプトアナリシス）