Index Calculus
El método de cálculo de índices resuelve logaritmos discretos en Z_p^* usando una base de factorización y álgebra lineal, con complejidad subexponencial L_p[1/2,√2].
Propósito
Superar a los algoritmos genéricos para logaritmos discretos en cuerpos primos, orientando la selección de parámetros DSA/DH.
Mecanismo
Se elige una base de factorización S={primos pequeños}. Se toman k aleatorios y se calcula g^k mod p; si el resultado es S-liso, produce una relación lineal ∑e_i·log(s_i)≡k (mod p−1). Se reúnen suficientes relaciones, se resuelven los log(s_i) con álgebra lineal y luego se calcula el log(h) objetivo.
Casos de uso
- Ataques de logaritmo discreto
- Criptoanálisis
- Algoritmos teórico-numéricos