Logaritmo discreto

En álgebra abstracta, se conoce como logaritmo discreto de y en base g, donde g e y son elementos de un grupo cíclico finito G, a la solución x de la ecuación g^x = y. Esto, se puede denotar matemáticamente como:

$x=\log_g(y)$

Los logaritmos discretos son análogos en teoría de grupos a los logaritmos ordinarios en análisis. Mientras que el cálculo de su inversa — la exponenciación discreta — es una tarea muy sencilla en términos computacionales, el cálculo del logaritmo discreto no es tan sencillo. El hecho de aplicar aritmética modular hace el problema de hallar x «irresoluble» en un tiempo razonable, por esto se usa, al igual que otros problemas con algoritmos poco eficientes, en criptografía, en el método de intercambio de claves de Diffie-Hellman o en el sistema de ElGamal.

Definición

La definición formal es la siguiente:

Sea (G,·) un grupo cíclico finito de orden n — con n elementos — y donde · es el operador multiplicación, es decir, el grupo G={e,g,g²,...,g^n-1}. Puesto que (G,·) es cíclico, tomando un generador g se sabe que para todo a perteneciente a G existe un k perteneciente a Z tal que a = g^k, o escrito de manera formal como:

$\forall a\in G \; \exists k\in \mathbb{Z}\;| \;a=g^k$.

Así pues, se define

$\log_g:G \rightarrow \mathbb{Z}/n\mathbb{Z}$

como la función que asigna valores de la siguiente manera:

$x\longmapsto k$ tal que $x \equiv g^k \mod n$.

Propiedades

Algunas de las propiedades de esta función son:

• $\log_g(x\cdot y)=\log_g(x)+\log_g(y)$

• $\forall\ t\in\mathbb{N},\log_g(c^t)=t\,\log_g(c)$

• $\log_g(1)=0$

• $\log_g(g)=1$

Aquí sigue vigente la fórmula del cambio de base de los logaritmos continuos siempre que c sea otro generador:

• $\log_c(x)=\log_c(g)\cdot \log_g(x)$

Véase también

• Logaritmo
• Raíz primitiva módulo n

Enlaces externos

• Weisstein, Eric W. «Discrete Logarithm» (en inglés). MathWorld. Wolfram Research.
• Discrete Logarithm en PlanetMath