Ir al contenido

Implementación de algoritmos de teoría de números/Logaritmo discreto

De Wikilibros, la colección de libros de texto de contenido libre.

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: