Logaritmo discreto

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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:

x=\log_g(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 tan sencillo. El hecho de aplicar aritmética modular hace el problema de hallar x «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.

Ejemplo[editar]

Los Logaritmos discretos son quizás más sencillos de entender en el grupo (Zp)×. Este es el grupo multiplicativo módulo primo p Sus elementos son de la clase de congruencia módulo p y el producto del grupo de dos elementos se consigue mediante la multiplicación de enteros seguido de la reducción módulo p.

La kth exponencial de uno de los números en este grupo, puede ser computada encontrado la exponencial kth como un entero y luego obtenido 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)×.

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, 16 es el menor número entero positivo m que cumple 3m ≡ 1 (mod 17), esto es 16 es de 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).

Definición[editar]

La definición formal es la siguiente:

Sea (G,·) un grupo cíclico finito de orden n — con n elementos — y donde · es el operador multiplicación, es decir, el grupo G={e,g,g2,...,gn-1}. Puesto que (G,·) es cíclico, tomando un generador g se sabe que para todo a perteneciente a G existe un k perteneciente a Z tal que a = gk, o escrito de manera formal como:

\forall a\in G \; \exists k\in \mathbb{Z}\;| \;a=g^k.

Así pues, se define

\log_g:G \rightarrow \mathbb{Z}/n\mathbb{Z}

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

x\longmapsto k tal que  x \equiv g^k \mod n.

Propiedades[editar]

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)

Algoritmos[editar]

No se conocen algoritmos clásicos para la computación de un algoritmo discretos logb 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).

(links en inglés salvo la Criba general del cuerpo de números por su inexistencia en Español)

Comparación con la factorización de enteros[editar]

Mientras que el problema del cálculo de logaritmos discretos y el problema de factorización de enteros son problemas distintos, comparten algunas propiedades:

  • ambos problemas son difíciles
  • para ambos problemas 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[editar]

Existen grupos para los que calcular logaritmos discretos es aparentemente difícil. En algunos casos (e.g. subgrupo de orden un primo grande del grupo(Zp)×) no hay ningún algoritmo eficaz conocido para el caso más difícil, y además, la complejidad en el caso promedio (para primos p escogidos al azar) resulta tan difícil como en el peor de los casos.

Al mismo tiempo, el problema inverso de 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 los grupos cíclicos (Zp)× (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[editar]

Enlaces externos[editar]

  1. «Tiempo Polinómico para el calculo de algoritmos discretos y la factorización de números primos». SIAM Journal on Computing 26 (5):  pp. 1484–1509. 1997.