El problema computacional de hallar un exponente k en un grupo multiplicativo finito G tal que g^k = h para una base g dada y un elemento h; es la inversión de la exponenciación en ese grupo.

Principio

Aprovechar la estructura del grupo: algoritmos genéricos (baby‑step giant‑step, Pollard rho) con complejidad aproximada de raíz cuadrada del orden del grupo, y reducciones dependientes de estructura (Pohlig–Hellman, index calculus) cuando el orden tiene factores pequeños o forma especial.

Demostración

Ejemplo en (Z/23Z)^×: g=5 y h=8. Cálculo de potencias: 5^1=5, 5^2=2, 5^3=10, 5^4=4, 5^5=20, 5^6=8, por tanto k=6 y 5^6≡8 (mod 23).

Aplicación incorrecta

Ejecutar algoritmos de logaritmo discreto sin verificar que g genera el subgrupo relevante (un g no generador no da k único), o aplicar index calculus en grupos donde no es efectivo (por ejemplo, ciertas curvas elípticas generales).

Consecuencia

La dureza o facilidad computacional del logaritmo discreto sustenta primitivas criptográficas (intercambio de claves, firmas) y condiciona parámetros de seguridad; algoritmos eficientes quebrantan estos sistemas o permiten cálculos eficaces en teoría de números.

Inversión

La exponenciación (calcular g^k) es la operación directa fácil; invertirla (logaritmo discreto) suele ser mucho más difícil, subrayando la asimetría entre operaciones de grupo y sus inversas en complejidad computacional.

Límite

Definido para grupos multiplicativos finitos o subgrupos cíclicos; la complejidad y los métodos dependen del orden del grupo, de su factorización y de la representación (cuerpos finitos, curvas elípticas); excluye grupos continuos y modelos aditivos sin isomorfismo adecuado.

Tensión semántica

Tensión entre la dureza genérica (algoritmos de coste raíz cuadrada) y la tratabilidad en casos estructurados (ordenes lisas, index calculus); la seguridad práctica equilibra estas tendencias opuestas.

Síntesis

El cálculo del logaritmo discreto es la inversión de la exponenciación en grupos finitos: un problema algorítmico cuya resolubilidad depende de la estructura del grupo y que se aborda con una gama de algoritmos genéricos y especializados de complejidades muy distintas.