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 g^x = 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

Sea (G,·) un grupo cíclico finito de orden n — con n elementos —, es decir, G={e,g,g²,...,g^n-1} para cierto elemento g de G. Dado h perteneciente a G existe un k perteneciente a Z tal que h = g^k. Este valor de k es el logaritmo discreto de h en base g.

Más formalmente, se define:

${\log }_g:G\to \mathbb{Z}/n\mathbb{Z}$

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

${\log }_g(x)=k$ tal que $x=g^k$.

Propiedades

Algunas de las propiedades de esta función son:

• ${\log }_g(x\cdot y)={\log }_g(x)+{\log }_g(y)$

• $\mathrm{\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)$