Logaritmo discreto
El logaritmo discreto es una variante del logaritmo clásico, que se utiliza al trabajar con números enteros en un campo finito o en un grupo finito.
De forma más precisa, si \( G \) es un grupo cíclico de orden \( n \) y \( g \) es un generador de \( G \), entonces para cualquier elemento \( a \in G \), el logaritmo discreto \( x \) es el entero que satisface:
\[ g^x \equiv a \mod n \]
donde \( x \) pertenece al intervalo \( [0, n-1] \).
Todo elemento de \( G \) se puede expresar como \( g^k \), para algún entero \( k \).
El logaritmo discreto de un elemento \( a \), en base \( g \), denotado como logg(a), es el exponente \( x \) tal que \( g^x = a \) dentro del grupo.
¿Para qué sirve? El logaritmo discreto es fundamental en teoría de números y en criptografía. Su gran utilidad reside en que constituye un problema computacionalmente difícil, lo que lo convierte en la base de muchas funciones unidireccionales en sistemas criptográficos. Mientras que calcular \( g^x \mod n \) es relativamente sencillo, hallar la inversa - es decir, encontrar \( x \) tal que \( g^x = y \mod n \), o equivalentemente \( x = \log_g(y) \mod n \) - es extraordinariamente complicado. Esta asimetría es la que garantiza la seguridad de numerosos protocolos criptográficos.
Ejemplo práctico
Consideremos un grupo cíclico sobre un campo finito de 11 elementos, en el cual las operaciones se realizan módulo 11:
$$ G = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11) $$
En este sistema, \( 10 + 1 \mod 11 = 11 \), pero \( 11 + 1 \mod 11 = 1 \), ya que en la aritmética modular los valores se repiten de forma cíclica.
Asimismo, podemos calcular potencias en este grupo:
$$ 2^1 \mod 11 = 2 $$
$$ 2^2 \mod 11 = 4 $$
$$ 2^3 \mod 11 = 8 $$
$$ 2^4 \mod 11 = 5 $$
Nota: En aritmética habitual, \( 2^4 = 16 \), pero al trabajar módulo 11, reducimos \( 16 \mod 11 = 5 \).
Ahora queremos calcular el logaritmo discreto de 9 en base 2, módulo 11. Es decir, buscamos un \( x \) tal que:
$$ 2^x \equiv 9 \mod 11 $$
Para resolverlo, probamos sucesivamente los exponentes:
$$ 2^1 \mod 11 = 2 $$
$$ 2^2 \mod 11 = 4 $$
$$ 2^3 \mod 11 = 8 $$
$$ 2^4 \mod 11 = 5 $$
$$ 2^5 \mod 11 = 10 $$
$$ 2^6 \mod 11 = 9 $$
Por tanto, el logaritmo discreto de 9 en base 2, módulo 11, es 6.
Verificación: En aritmética clásica, \( 2^6 = 64 \). Al reducir módulo 11: \( 64 \mod 11 = 64 - 5 \cdot 11 = 64 - 55 = 9 \), con lo cual se verifica que: $$ 2^6 \mod 11 = 9 $$ Si construimos la tabla de multiplicación modular de este grupo, observaremos que: \( 8 \times 8 \mod 11 = 9 \), lo cual confirma el resultado.
Este ejemplo muestra cómo funciona el logaritmo discreto.
También ilustra por qué, aunque verificar que \( 2^6 \equiv 9 \mod 11 \) es sencillo, encontrar \( x \) se vuelve un problema sumamente complejo cuando se trabaja con números mucho mayores - como ocurre en aplicaciones criptográficas.
Y así sucesivamente.
