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 gx = y. Esto, se puede denotar matemáticamente como:
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.
Índice |
Definición [editar]
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,g2,...,gn-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 = gk, o escrito de manera formal como:
.
Así pues, se define
como la función que asigna valores de la siguiente manera:
tal que
.
Propiedades [editar]
Algunas de las propiedades de esta función son:
Aquí sigue vigente la fórmula del cambio de base de los logaritmos continuos siempre que c sea otro generador:
Véase también [editar]
Enlaces externos [editar]
- Weisstein, Eric W. «Discrete Logarithm» (en inglés). MathWorld. Wolfram Research.
- Discrete Logarithm en PlanetMath

.
tal que
.



