Logaritmo discreto

Se conoce como logaritmo discreto de x en base a módulo n a resolver la ecuación x=a^y mod n donde x,n y a son constantes e y es la incógnita. A partir de ahora notaremos esta situación como:

$y=\operatorname{log\;disc}_a(x)$

El hecho de aplicar aritmética modular hace el problema de hallar y «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.

Definición

La definición formal es la siguiente:

Sea (G,*) un grupo cíclico finito con n elementos y donde * es el operador multiplicación, es decir G={e,g,g²,...,g^n-1}. Puesto que (G,*) es cíclico, se sabe que para todo a perteneciente a G existe un k perteneciente a Z tal que a = g^k, o escrito de manera formal como $\forall a\in G \; \exists k\in \mathbb{Z}\;| \;a=g^k$. Así pues, se define $\operatorname{log\;disc}_g:G \rightarrow \mathbb{Z}/n\mathbb{Z}$ como la función que asigna valores de la siguiente manera:

$x\longmapsto k$ tal que $x=g^k \mod n$.

Propiedades

Algunas de las propiedades de esta función son:

$\operatorname{log\;disc}_g(x*y)=\operatorname{log\;disc}_g(x)+\operatorname{log\;disc}_g(y)$

$\forall\ t\in\mathbb{N},\operatorname{log\;disc}_g(c^t)=t\,\operatorname{log\;disc}_g(c)$

$\operatorname{log\;disc}_g(1)=0$

$\operatorname{log\;disc}_g(g)=1$

Aquí sigue vigente la fórmula del cambio de base de los logaritmos continuos siempre que c sea otro generador:

$\operatorname{log\;disc}_c(x)=\operatorname{log\;disc}_c(g)*\operatorname{log\;disc}_g(x)$

Véase también

• Logaritmo
• Raíz primitiva módulo n