En matemáticas , por dadas números reales a y b , el logaritmo log b un es un número x de tal manera que b x = un . De manera análoga, 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 un (mod m ) (leer "el índice de una a la base r modulo m ") para r x ≡ un (mod m ) si r es una raíz primitiva de m y gcd ( una , m ) = 1.
Los logaritmos discretos se pueden calcular rápidamente en algunos casos especiales. Sin embargo, no se conoce ningún método eficaz para calcularlos en general. Varios algoritmos importantes en criptografía de clave pública basan su seguridad en el supuesto de que el problema del logaritmo discreto sobre grupos cuidadosamente elegidos no tiene una solución eficiente [ cita requerida ] .
Sea G cualquier grupo. Denotemos su operación de grupo por multiplicación y su elemento de identidad por 1. Sea b ser 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 .
Vamos a ser también un elemento de G . Un número entero k que resuelve la ecuación b k = a se denomina logaritmo discreto (o simplemente logaritmo , en este contexto) de a a la base b . Se 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.