Calculadora de logaritmos discretos

  1. Alpertron
  2. Programas
  3. Calculadora de logaritmos discretos

Esta aplicación Web calcula logaritmos discretos.

El problema de los logaritmos discretos consiste en hallar el exponente en la expresión BaseExponente = Potencia (mod Módulo).

Esta aplicación funciona para modulos primos y compuestos. La única restricción es que la base y el módulo, y la potencia y el módulo deben ser primos entre sí.

En esta versión de la calculadora de logaritmos discretos está implementado el algoritmo Pohlig-Hellman, así que el tiempo de ejecución es proporcional a la raíz cuadrada del mayor factor primo del módulo menos 1. El applet responde en un período de tiempo razonable si este factor es menor que 1017.

Se pueden ingresar expresiones que usen los siguientes operadores y paréntesis:

  • + para suma
  • - para resta
  • * para multiplicación
  • / para división entera
  • % para el resto de la división entera
  • ^ o ** para exponenciación (el exponente debe ser mayor o igual que cero).
  • <, ==, >; <=, >=, != para comparaciones. Los operadores devuelven cero si es falso y -1 si es verdadero.
  • AND, OR, XOR, NOT para lógica binaria. Las operaciones se hacen en binario (base 2). Se agregan infinitos ceros (unos) a la izquerda de los números positivos (negativos).
  • SHL o <<: Si b ≥ 0, a SHL b desplaza el valor a a la izquierda la cantidad de bits especificada por b. Esto equivale a a × 2b. En caso contrario, a SHL b desplaza el valor a a la derecha la cantidad de bits especificada por −b. Esto equivale a floor(a / 2b). Ejemplo: 5 SHL 3 = 40.
  • SHR o >>: Si b ≥ 0, a SHR b desplaza el valor a a la derecha la cantidad de bits especificada por b. Esto equivale a floor(a / 2b). En caso contrario, a SHR b desplaza el valor a a la izquierda la cantidad de bits especificada por −b. Esto equivale a a × 2b. Ejemplo: -19 SHR 2 = -5.
  • n!: factorial (n debe ser mayor o igual que cero). Ejemplo: 6! = 6 × 5 × 4 × 3 × 2 = 720.
  • n!! ... !: factorial múltiple (n debe ser mayor o igual que cero). Es el producto de n por nk por n2k ... (todos los números son mayores que cero) donde k es la cantidad de signos de exclamación. Ejemplo: 7!! = 7 × 5 × 3 × 1 = 105.
  • p#: primorial (producto de todos los primos menores o iguales a p). Ejemplo: 12# = 11 × 7 × 5 × 3 × 2 = 2310.
  • B(n): Número probablemente primo anterior a n. Ejemplo: B(24) = 23.
  • F(n): Número de Fibonacci Fn que corresponde a la secuencia 0, 1, 1, 2, 3, 5, 8, 13, 21, etc. donde cada elemento es igual a la suma de los dos anteriores. Ejemplo: F(7) = 13.
  • L(n): Número de Lucas Ln = Fn-1 + Fn+1
  • N(n): Número probablemente primo posterior a n. Ejemplo: N(24) = 29.
  • P(n): particiones irrestrictas (cantidad de descomposiciones de n en sumas de números enteros sin tener en cuenta el orden). Ejemplo: P(4) = 5 porque el número 4 se puede particionar de 5 formas distintas: 4 = 3+1 = 2+2 = 2+1+1 = 1+1+1+1.
  • Gcd(m,n, ...): Máximo común divisor de estos números enteros. Ejemplo: GCD(12,16) = 4.
  • Lcm(m,n, ...): Mínimo común múltiplo de estos números enteros. Ejemplo: LCM(12,16,24) = 48.
  • Modinv(m,n): inverso de m modulo n, sólo válido cuando m y n son coprimos, es decir que no tienen factores en común. Ejemplo: Modinv(3,7) = 5 porque 3 × 5 ≡ 1 (mod 7)
  • Modpow(m,n,r): halla mn módulo r. Ejemplo: Modpow(3, 4, 7) = 4, porque 34 ≡ 4 (mod 7).
  • IsPrime(n): retorna cero si n no es un primo probable y -1 si lo es. Ejemplo: IsPrime(5) = -1.
  • Sqrt(n): parte entera de la raíz cuadrada del argumento.
  • NumDigits(n,r): cantidad de dígitos de n en base r. Ejemplo: NumDigits(13, 2) = 4 porque 13 en binario (base 2) se expresa como 1101.
  • SumDigits(n,r): suma de dígitos de n en base r. Ejemplo: SumDigits(213, 10) = 6 porque la suma de los dígitos expresados en decimal es 2+1+3 = 6.
  • RevDigits(n,r): halla el valor que se obtiene escribiendo para atrás los dígitos de n en base r. Ejemplo: RevDigits(213, 10) = 312.

Puedes usar el prefijo 0x para números hexadecimales, por ejemplo 0x38 es igual a 56.

El símbolo de exponenciación no está presente en algunos dispositivos móviles, así que es posible digitar dos asteriscos ** para el operador de exponenciación.

Ejemplo: Hallar el número n tal que 7n ≡ 23 (mod 43241).

Digita 7 en la caja de entrada de Base, 23 en la caja de Potencia y 43241 en la caja Mod. Luego aprieta el botón denominado "Logaritmo discreto".

El resultado es 3360 + 3930 k, donde k puede ser cualquier número entero. Como verificación puedes hallar 73360 ≡ 23 (mod 43241) y 73930 ≡ 1 (mod 43241)

Código fuente

Puedes bajar el código fuente del programa actual y del viejo applet de cálculo de logaritmos discretos desde GitHub. El código fuente está escrito en lenguaje C, por lo que es necesario Emscripten para generar Javascript.

Escrito por Dario Alpern. Actualizado el 26 de noviembre de 2021.

Si encuentra algún error o tiene algún comentario, por favor llene el formulario.