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 g^x = y. Esto, se puede denotar matemáticamente como:

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 se use en criptografía, en el método de intercambio de claves de Diffie-Hellman o en el sistema de ElGamal.

YouTube Encyclopedic

1/3
Views:
530
1 625
3 317

Transcription

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₁₇)^×, para considerar 3⁴ en este grupo, primero se calcula 3⁴ = 81 y después se divide 81 entre 17 obteniendo de resto 13. Esto es 3⁴ = 13 en el grupo (Z₁₇)^×. 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¹⁶ ≡ 1 (mod 17) — como indica el Pequeño teorema de Fermat — , se deduce que, si n es un entero, entonces 3⁴⁺¹⁶ⁿ ≡ 3⁴ × (3¹⁶)ⁿ ≡ 13 × 1ⁿ ≡ 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 3^m ≡ 1 (mod 17) (en otras palabras, 16 es el orden de 3 en (Z₁₇)^×), estas son las únicas soluciones. Equivalentemente, el conjunto de todas las posibles soluciones puede ser expresado por la restricción k ≡ 4 (mod 16).

Definición

Sea (G,·) un grupo cíclico finito de orden n — con n elementos —, es decir, G={e,g,g²,...,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\rightarrow \mathbb {Z} /n\mathbb {Z}

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

\log _{g}(x)=k

tal que

x\equiv g^{k}

Propiedades

Algunas de las propiedades de esta función son:

$\log _{g}(x\cdot y)=\log _{g}(x)+\log _{g}(y)$

$\forall \ t\in \mathbb {N} ,\log _{g}(c^{t})=t\,\log _{g}(c)$

$\log _{g}(1)=0$

$\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)\cdot \log _{g}(x)$

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.^[1]

Existen algoritmos más sofisticados, normalmente inspirados por algoritmos similares para la factorización de enteros. Estos algoritmos funcionan más rápido que el algoritmo anterior. Algunos de ellos en un tiempo lineal respecto de la raíz cuadrada del tamaño del grupo y, por lo tanto, exponencial respecto de la mitad del número de dígitos del tamaño del grupo. Sin embargo, ninguno corre en un Tiempo polinómico (en el número de dígitos del tamaño del grupo). Algunos de los algoritmos funcionan para cualquier grupo, mientras otros sólo pueden ser utilizados para ciertos grupos concretos.^[2]

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

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:

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

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 a 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).

Véase también

Referencias

↑ Shor, Peter (1997). «Tiempo Polinómico para el cálculo de algoritmos discretos y la factorización de números primos». SIAM Journal on Computing 26 (5): 1484-1509. arXiv:quant-ph/9508027.
↑ Stinson, Douglas (2006). «Algorithms for the discret logarithm problem». Cryptography: theory and practice (en inglés) (tercera edición). Chapman & Hall/ CRC. pp. 236-246. ISBN 978-1-58488-508-5.