Logaritmo discreto

Al igual que los logaritmos comunes en base 10, en la aritmética modular el logaritmo de un número n respecto al módulo $m$  es la solución $x=g$ a la ecuación $a^x\equiv b\pmod m$, donde la base $a$ es una raíz primitiva del módulo $m$ que genera (con sus potencias) todos los elementos inversibles del sistema de residuos (respecto a un módulo m).

Esto es así porque cada uno de los elementos inversibles queda representado por el exponente al que se eleva la raíz primitiva para obtener ese elemento: se tiene una correspondencia biunívoca entre los exponentes y los elementos inversibles. De esta manera, si $a$ es raíz primitiva y $b$ un elemento inversible, entonces existe un exponente $g$ tal que $a^g = b.$  A ese número $g$ se le llama logaritmo discreto de $b$ con base $a$ (la raíz primitiva).

En resumen, en módulo $m$, el logaritmo discreto de $n$ es el exponente al que hay que elevar la base $a$ para obtener $n$.  Es la solución a la ecuación de congruencias $a^x\equiv b\pmod m$.)

Para el módulo 7, el residuo 3 es una raíz primitiva de 7 (que el lector lo verifique) y genera, mediante sus potencias, todos los elementos inversibles desde 1 a 6 (por ser 7 primo son todos inversibles), lo que posibilita encontrar los logaritmos discretos para todos ellos. Por ejemplo, como 3^4 = 4, se tiene que $log_4(4) = 4$.