Pohlig-Hellman Algorithm
Pohlig-Hellman décompose un logarithme discret dans un groupe d'ordre friable en logarithmes discrets dans chaque sous-groupe d'ordre puissance de nombre premier, puis les fusionne avec le CRT.
Objectif
Accélérer les logarithmes discrets dans les groupes d'ordre friable et guider le choix de paramètres de groupe sûrs.
Mécanisme
Si l'ordre du groupe est n=∏p_i^e_i, on résout x mod p_i^e_i séparément (avec BSGS dans le sous-groupe d'ordre p_i^e_i), puis on fusionne via le CRT. Ainsi, les paramètres DH doivent avoir un ordre contenant un grand facteur premier.
Cas d’usage
- Accélération du logarithme discret
- Sécurité des paramètres DH
- Cryptanalyse