ⓘ 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, la solución ..

                                     

ⓘ 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, la solución x de la ecuación g x = y. Esto, se puede denotar matemáticamente como:

x = log g ⁡ y ⟺ g x = y {\displaystyle x=\log _{g}y\Longleftrightarrow 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. El hecho de que el problema sea "irresoluble" en un tiempo razonable si se utiliza aritmética modular hace que esto use en criptografía, en el método de intercambio de claves de Diffie-Hellman o en el sistema de ElGamal.

                                     

1. Ejemplo

Los Logaritmos discretos son quizás más sencillos de entender en el grupo Z p ×, 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 Z 17 ×, para considerar 3 4 en este grupo, primero se calcula 3 4 = 81 y después se divide 81 entre 17 obteniendo de resto 13. Esto es 3 4 = 13 en el grupo Z 17 ×. 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 3 k ≡ 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 3 16 ≡ 1 mod 17 - como indica el Pequeño teorema de Fermat -, se deduce que, si n es un entero, entonces 3 4+16 n ≡ 3 4 × 3 16 n ≡ 13 × 1 n ≡ 13 mod 17. Por lo tanto la ecuación tiene infinitas soluciones de la forma 4 + 16 n. Por otra parte, como 16 es el menor número entero positivo m que cumple 3 m ≡ 1 mod 17 en otras palabras, 16 es el orden de 3 en Z 17 ×), estas son las únicas soluciones. Equivalentemente, el conjunto de todas las posibles soluciones puede ser expresado por la restricción k ≡ 4 mod 16.

                                     

2. Definición

Sea G, un grupo cíclico finito de orden n - con n elementos -, es decir, G ={ e, g, g 2.,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 → Z / n Z {\displaystyle \log _{g}:G\rightarrow \mathbb {Z} /n\mathbb {Z} }

como la función que asigna valores de la siguiente manera:

log g ⁡ x = k {\displaystyle \log _{g}x=k} tal que x ≡ g k {\displaystyle x\equiv g^{k}}.
                                     

3. Propiedades

Algunas de las propiedades de esta función son:

  • log g ⁡ x ⋅ y = log g ⁡ x + log g ⁡ y {\displaystyle \log _{g}x\cdot y=\log _{g}x+\log _{g}y}
  • ∀ t ∈ N, log g ⁡ c t = t log g ⁡ c {\displaystyle \forall \ t\in \mathbb {N},\log _{g}c^{t}=t\,\log _{g}c}
  • log g ⁡ 1 = 0 {\displaystyle \log _{g}1=0}
  • log g ⁡ g = 1 {\displaystyle \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 ⋅ log g ⁡ x {\displaystyle \log _{c}x=\log _{c}g\cdot \log _{g}x}
                                     

4. Cálculo

No se conocen algoritmos clásicos para la computación de un logaritmo discreto log b g. Un algoritmo es elevar b a sucesivas potencias k hasta encontrar la deseada g. Este algoritmo requiere una complejidad temporal lineal respecto del tamaño del grupo G y, por lo tanto, exponencial respecto del número de dígitos en el tamaño del grupo. Existe un algoritmo cuántico eficiente debido a Peter Shor. ​

  • Baby-step giant-step también conocido como algoritmo de Shanks
  • Algoritmo Pohlig–Hellman
  • Algoritmo rho de Pollard para logaritmo discreto
  • Algoritmo de cálculo de índices
  • Algoritmo del canguro de Pollard también conocido como algoritmo lambda
                                     

5. Comparación con la factorización de enteros

Si bien los problema del cálculo de logaritmos discretos y el de factorización de enteros son distintos, comparten algunas propiedades:

  • para ambos se conocen algoritmos eficientes en ordenadores cuánticos,
  • la dificultad de ambos problemas se ha utilizado para construir varios sistemas criptográficos.
  • algoritmos para un problema a menudo se adaptan al otro, y
  • ambos problemas son difíciles
                                     

6. Criptografía

Existen grupos para los que calcular logaritmos discretos es aparentemente difícil. En algunos casos no hay ningún algoritmo eficaz conocido para resolver el problema en general y la complejidad en el caso promedio resulta tan difícil como en el peor de los casos.

Al mismo tiempo, el problema inverso, la exponenciación discreta, no es difícil puede ser computada eficientemente usando Exponenciación binaria. Esta asimetría es análoga la que ocurre entre la factorización de enteros y la multiplicación de enteros. Ambas asimetrías han sido explotadas en la construcción de sistemas criptográficos.

Opciones populares para el grupo G en la criptografía usando logaritmos discretos son aquellos para los que no existen buenos algoritmos, entre los que se encuentran los grupos cíclicos Z p × e.g. Cifrado ElGamal, Diffie-Hellman y el algoritmo de firma digital y subgrupos cíclicos de curvas elípticas sobre cuerpos finitos ver Criptografía de curva elíptica.