Logaritmo discreto

De Wikipedia, la enciclopedia libre

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=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.

Una definición más rigurosa es la siguiente: Sea $(G, * )$ un grupo cíclico finito con $n$ elementos y donde $*$ es la multiplicación, es decir $G = {e, g, g 2,..., g n - 1}$ . Como hemos dicho que $(G, * )$ es cíclico sabemos que $\forall a\in G \; \exists k\in \mathbb{Z}\;|\;a=g^k$ . Entonces definimos $log \ disc_g:G \rightarrow \mathbb{Z}/n\mathbb{Z}$ como la función que asigna valores de la siguiente manera $x\longmapsto k\; |\; x=g^k\; mod\; n$