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\rightarrow \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)$

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