En matemáticas , para números reales dados a y b , el logaritmo log b a es un número x tal que b x = a . Análogamente, en cualquier grupo G , las potencias b k pueden definirse para todos los enteros k , y el logaritmo discreto log b a es un entero k tal que b k = a . En teoría de números , el término más comúnmente utilizado esíndice : podemos escribir x = ind r a (mod m ) (léase "el índice de a a la base r módulo m ") para r x ≡ a (mod m ) si r es una raíz primitiva de m y mcd ( a , m ) = 1.
Los logaritmos discretos son rápidamente computables en algunos casos especiales. Sin embargo, no se conoce ningún método eficiente para calcularlos en general. Varios algoritmos importantes en criptografía de clave pública , como El Gamal , basan su seguridad en la suposición de que el problema del logaritmo discreto sobre grupos cuidadosamente elegidos no tiene una solución eficiente.
Sea G cualquier grupo. Denote su operación de grupo por multiplicación y su elemento de identidad por 1. Sea b cualquier elemento de G . Para cualquier entero positivo k , la expresión b k denota el producto de b consigo mismo k veces:
De manera similar, sea b − k el producto de b −1 consigo mismo k veces. Para k = 0, la k -ésima potencia es la identidad : b 0 = 1 .
Sea a también un elemento de G. Un entero k que resuelve la ecuación b k = a se denomina logaritmo discreto (o simplemente logaritmo , en este contexto) de a en base b . Uno escribe k = log b a .
Las potencias de 10 forman un subconjunto infinito G = {…, 0.001, 0.01, 0.1, 1, 10, 100, 1000,…} de los números racionales . Este conjunto G es un grupo cíclico bajo multiplicación, y 10 es un generador. Para cualquier elemento a del grupo, se puede calcular log 10 a . Por ejemplo, log 10 10000 = 4 y log 10 0,001 = −3. Estos son ejemplos del problema del logaritmo discreto.