Logaritmo discreto

Se conoce como logaritmo discreto de x en base a módulo n a resolver la ecuación x=a^y mod n donde x,n y a son constantes e y es la incógnita. A partir de ahora notaremos esta situación como:

$y=\operatorname{log\;disc}_a(x)$

El hecho de aplicar aritmética modular hace el problema de hallar y «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.

Definición

La definición formal es la siguiente:

Sea (G,*) un grupo cíclico finito con n elementos y donde * es el operador multiplicación, es decir G={e,g,g²,...,g^n-1}. Puesto que (G,*) es cíclico, se sabe que para todo a perteneciente a G existe un k perteneciente a Z tal que a = g^k, o escrito de manera formal como $\forall a\in G \; \exists k\in \mathbb{Z}\;| \;a=g^k$ . Así pues, se define $\operatorname{log\;disc}_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=g^k \mod n$ .

Propiedades

Algunas de las propiedades de esta función son:

$\operatorname{log\;disc}_g(x*y)=\operatorname{log\;disc}_g(x)+\operatorname{log\;disc}_g(y)$

$\forall\ t\in\mathbb{N},\operatorname{log\;disc}_g(c^t)=t\,\operatorname{log\;disc}_g(c)$

$\operatorname{log\;disc}_g(1)=0$

$\operatorname{log\;disc}_g(g)=1$

Aquí sigue vigente la fórmula del cambio de base de los logaritmos continuos siempre que c sea otro generador:

$\operatorname{log\;disc}_c(x)=\operatorname{log\;disc}_c(g)*\operatorname{log\;disc}_g(x)$

Véase también

Categorías:

Funciones especiales
Logaritmos

Wikimedia foundation. 2010.

Игры ⚽ Поможем написать реферат

Mira otros diccionarios:

Logaritmo discreto — El logaritmo discreto consiste en resolver la ecuación: a = bx mod n donde a, b y n son constantes y x es la incógnita que se busca. Es clara la similitud de esta ecuación con la del logaritmo. Sin embargo, el uso de aritmética modular introduce… … Enciclopedia Universal
Logaritmo complejo — Una única rama del logaritmo complejo. El tono del color se utiliza para mostrar el argumento (ángulo de coordenadas polares) del logaritmo complejo. La intensidad del color se utiliza para mostrar el módulo del logaritmo complejo. La página con… … Wikipedia Español
Complejidad y criptografía — La criptografía es la ciencia encargada del estudio y diseño de sistemas que permiten ocultar información. Desde sus inicios, esta capacidad de encubrimiento se ha basado en la dificultad que supondría a una entidad no autorizada el obtener la… … Wikipedia Español
Criptografía de curva elíptica — Saltar a navegación, búsqueda La Criptografía de Curva Elíptica (CCE) es una variante de la criptografía asimétrica o de clave pública basada en las matemáticas de las curvas elípticas. Sus autores argumentan que la CCE puede ser más rápida y… … Wikipedia Español
Número primo fuerte — Este artículo o sección sobre matemáticas necesita ser wikificado con un formato acorde a las convenciones de estilo. Por favor, edítalo para que las cumpla. Mientras tanto, no elimines este aviso puesto el 10 de septiembre de 2009. También… … Wikipedia Español
Diffie-Hellman — Saltar a navegación, búsqueda El protocolo Diffie Hellman[1] (debido a Whitfield Diffie y Martin Hellman) permite el intercambio secreto de claves entre dos partes que no han tenido contacto previo, utilizando un canal inseguro, y de manera… … Wikipedia Español
Cifrado ElGamal — Este artículo o sección necesita referencias que aparezcan en una publicación acreditada, como revistas especializadas, monografías, prensa diaria o páginas de Internet fidedignas. Puedes añadirlas así o avisar … Wikipedia Español
Criptoanálisis — Saltar a navegación, búsqueda Criptoanálisis (del griego kryptós, escondido y analýein, desatar ) es el estudio de los métodos para obtener el sentido de una información cifrada, sin acceso a la información secreta requerida para obtener este… … Wikipedia Español
Aritmética Modular Compleja — Saltar a navegación, búsqueda La ‘Aritmética Modular Compleja’ (hacia un nuevo test de primalidad) Contenido 1 La ‘Aritmética Modular Compleja’.La ‘semiarcotangente discreta’ 2 El Indicador imaginario de Euler´: IiE (M) … Wikipedia Español
BQP — Saltar a navegación, búsqueda En Teoría de la complejidad computacional, BQP representa la clase de algoritmos que pueden ser resueltos en un computador cuántico en tiempo polinómico con un margen de error promedio inferior a 1/4. Dicho de otra… … Wikipedia Español

Los diccionarios y las enciclopedias sobre el Académico

Logaritmo discreto

Definición

Propiedades

Véase también

Mira otros diccionarios:

Compartir el artículo y extractos

Los diccionarios y las enciclopedias sobre el Académico

Wikipedia Español

Logaritmo discreto

Definición

Propiedades

Véase también

Mira otros diccionarios:

Compartir el artículo y extractos

Link directo