Logaritmo discreto

En álgebra abstracta, se conoce como 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 gx = y. Esto, se puede denotar matemáticamente como:

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. El hecho de que el problema sea «irresoluble» en un tiempo razonable si se utiliza aritmética modular hace que esto se use en criptografía, en el método de intercambio de claves de Diffie-Hellman o en el sistema de ElGamal.

Ejemplo

Los Logaritmos discretos son quizás más sencillos de entender en el grupo (Zp)×, o sea el grupo multiplicativo módulo un primo p.

La k-ésima potencia de uno de los números en este grupo puede ser calculada encontrando la potencia k-ésima como un entero y luego obteniendo el resto después de su división por p. Este proceso es llamado Exponenciación modular. Por ejemplo, considerando (Z17)×, para considerar 34 en este grupo, primero se calcula 34 = 81 y después se divide 81 entre 17 obteniendo de resto 13. Esto es 34 = 13 en el grupo (Z17)×. En la práctica se utiliza el método de la exponenciación binaria, reduciendo en cada paso.

El logaritmo discreto es la operación inversa. Por ejemplo, considerando la ecuación 3k ≡ 13 (mod 17) para k. Del ejemplo de arriba, una solución es k = 4, pero esta no es la única solución. Puesto que 316 ≡ 1 (mod 17) — como indica el Pequeño teorema de Fermat — , se deduce que, si n es un entero, entonces 34+16n ≡ 34 × (316)n ≡ 13 × 1n ≡ 13 (mod 17). Por lo tanto la ecuación tiene infinitas soluciones de la forma 4 + 16n. Por otra parte, como 16 es el menor número entero positivo m que cumple 3m ≡ 1 (mod 17) (en otras palabras, 16 es el orden de 3 en (Z17)×), estas son las únicas soluciones. Equivalentemente, el conjunto de todas las posibles soluciones puede ser expresado por la restricción k ≡ 4 (mod 16).

Other Languages