Pohlig-Hellman Algorithm
Pohlig-Hellman descompone un logaritmo discreto en un grupo de orden suave en logaritmos discretos en cada subgrupo de orden potencia de primo, y luego los fusiona con el CRT.
Propósito
Acelerar los logaritmos discretos en grupos de orden suave y orientar la selección de parámetros de grupo seguros.
Mecanismo
Si el orden del grupo es n=∏p_i^e_i, se resuelve x mod p_i^e_i por separado (con BSGS en el subgrupo de orden p_i^e_i) y se fusiona con el CRT. Por ello, los parámetros DH deben tener un orden con un factor primo grande.
Casos de uso
- Aceleración del logaritmo discreto
- Seguridad de parámetros DH
- Criptoanálisis