Implementación de algoritmos de teoría de números/Logaritmo discreto
El 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. 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 sencillo en muchos grupos.
Definición
[editar]Sea (G,·) un grupo cíclico finito de orden n — con n elementos —, es decir, G={e,g,g2,...,gn-1} para cierto elemento g de G. Dado h perteneciente a G existe un k perteneciente a Z tal que h = gk. Este valor de k es el logaritmo discreto de h en base g.
Más formalmente, 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: