Solucionador de logaritmo discreto
Si pregunta qué potencia de 2 deja 5 módulo 13, obtiene 9, porque 2^9 ≡ 5 (mod 13). Escriba una base, un objetivo y un módulo primo para hallar el menor exponente, con una igualdad que puede comprobar. Gratis en su navegador.
- Gratis
- Funciona en su navegador
- Sin registro
- Sus datos no salen de su equipo
Ejecutar — gratis
Ejemplo resuelto
- G
- 2
- H
- 5
- Potencia (W)
- 13
- X
- 9
- Ecuación
- 2^9 ≡ 5 (mod 13)
El problema del logaritmo discreto busca un entero x tal que una base dada g elevada a x sea congruente con un objetivo h módulo un primo p. Sustenta el intercambio de claves de Diffie–Hellman, el cifrado ElGamal y muchos ejercicios de libro de la criptografía algebraica. Esta capacidad implementa el clásico algoritmo de paso enano, paso gigante: una búsqueda determinista, en tiempo de raíz cuadrada, que recupera el menor exponente no negativo o demuestra que h no es una potencia de g en el grupo multiplicativo módulo p.
Qué pide el logaritmo discreto
Dados los enteros g, h y un primo p, el logaritmo discreto de h en base g módulo p es cualquier entero x que satisface g elevado a x congruente con h módulo p. Cuando existe una solución, el menor representante no negativo en el rango de cero a p menos dos es único una vez fijado ese rango, y es el valor que devuelve esta herramienta.
A diferencia de los logaritmos reales corrientes, no hay una fórmula elemental cerrada que sirva para primos arbitrarios; la dificultad de recuperar x para primos grandes cuidadosamente elegidos es precisamente lo que hace útil a la criptografía de logaritmo discreto.
Sin embargo, en la enseñanza y en experimentos con parámetros pequeños, usted todavía necesita un solucionador correcto e inspeccionable: uno que valide la hipótesis de primalidad, reduzca las entradas al sistema canónico de residuos, busque de forma sistemática y, o bien imprima un exponente verificable, o bien indique con claridad que no existe solución.
Cómo encuentra x el paso enano, paso gigante
El paso enano, paso gigante reescribe el exponente desconocido como x igual a i por m más j, donde m es aproximadamente la raíz cuadrada del orden del grupo p menos uno, y tanto i como j recorren de cero hasta m. El algoritmo primero almacena cada valor enano g elevado a j módulo p en una tabla hash indexada por residuo, y luego avanza en pasos gigantes multiplicando repetidamente el objetivo por el inverso modular de g elevado a m, y buscando cada residuo intermedio en la tabla.
Una coincidencia proporciona tanto i como j y, por tanto, x. Las bases y los objetivos fuera de cero a p menos uno se reducen módulo p, y la respuesta refleja la g, la h y la p reducidas para que quienes llaman puedan auditar la instancia exacta que se resolvió.
Entradas, límites, precio y cuándo no hay solución
Los campos obligatorios son g (base), h (residuo objetivo) y p (módulo primo). Se aceptan cadenas de dígitos para enteros grandes dentro del límite del módulo. Si h no está en el subgrupo cíclico generado por g módulo p —por ejemplo, cuando g genera solo un subgrupo propio y h queda fuera de él—, el solucionador devuelve solved false con un exponente nulo y un mensaje explicativo en lugar de fabricar una x incorrecta.
Ese resultado es un cálculo correcto, no un error del cliente, porque la entrada estaba bien formada y la respuesta matemática es que no existe logaritmo. Los errores del cliente abarcan campos faltantes, valores no enteros, módulos fuera del rango permitido y p compuesto. La herramienta en el navegador ejecuta la biblioteca idéntica de forma gratuita y sin cuenta.
Use el resultado para revisar tareas, generar pruebas de respuesta conocida para bibliotecas de criptografía o explorar la pertenencia a subgrupos antes de escalar parámetros en el diseño de un protocolo real.
Qué puede hacer con ella
Verificación de tareas y exámenes
Estudiantes y docentes revisan ejercicios de logaritmo discreto como 2^x ≡ 5 (mod 13) y reciben tanto el exponente como una congruencia imprimible para el solucionario.
Pruebas de respuesta conocida para código de criptografía
Los autores de bibliotecas introducen instancias pequeñas de cuerpo primo en la CI para que la exponenciación modular y las funciones de inverso se mantengan consistentes con una referencia BSGS independiente.
Experimentos de pertenencia a subgrupos
Los investigadores prueban bases y objetivos candidatos módulo un primo pequeño para ver si h está en el subgrupo generado por g antes de pasar a parámetros de tamaño de producción.
Preguntas frecuentes
¿Qué algoritmo utilizan?
Paso enano, paso gigante (Shanks). Encuentra la menor x no negativa con g^x ≡ h (mod p) en tiempo y memoria de aproximadamente O(√p), tras una comprobación de primalidad determinista sobre p.
¿Qué ocurre si p no es primo?
Esta herramienta define el logaritmo discreto en el grupo multiplicativo de un cuerpo primo y no funcionará en silencio módulo un compuesto.
¿Y si no existe ningún exponente?
Obtiene solved: false y x: null con un mensaje breve. Es un resultado matemático válido (h no es potencia de g mod p), no un error de facturación ni de validación.
¿Cómo resuelvo 2^x ≡ 5 (mod 13)?
Escriba 2 como base, 5 como objetivo y 13 como módulo primo. La respuesta es 9: al elevar 2 a la novena potencia y dividir entre 13 queda resto 5, y ningún exponente menor lo consigue.
¿Hasta qué tamaño puede llegar el módulo primo?
Hasta cerca de un billón. Alcanza para tareas, explicaciones de protocolos y experimentos pequeños con respuesta rápida; no está pensado para los primos enormes que protegen el cifrado real.
Herramientas relacionadas
Para desarrolladores — acceso por API
Todo lo de esta página está disponible por programación. Esta sección es para equipos que quieren integrarlo en sus sistemas; el resto puede usar la herramienta de arriba sin más.
Endpoint de API
¿Prefiere automatizarlo? Un POST autenticado crea la tarea; el resultado llega por webhook o enlace firmado. La misma capacidad también se ejecuta aquí en la web, por email y desde Telegram — y pronto también desde nuestra app.
Llámela desde su stack
curl -X POST https://api.kit.forhosting.com/numth/discrete-log \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"g":2,"h":5,"p":13}'const res = await fetch("https://api.kit.forhosting.com/numth/discrete-log", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"g": 2,
"h": 5,
"p": 13
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/discrete-log",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"g": 2,
"h": 5,
"p": 13
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/discrete-log", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"g":2,"h":5,"p":13}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"g":2,"h":5,"p":13}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/discrete-log", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)Ejemplo de solicitud
{
"g": 2,
"h": 5,
"p": 13
}Ejemplo de respuesta
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.discrete_log",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}La API es asíncrona: la llamada devuelve un task_id al instante y el resultado llega por webhook. El polling está limitado a 1 req/s por tarea.
Precio
Precio publicado — sin tokens ni créditos inventados. Una tarea fallida no se cobra.
Límites
max_p | 1000000000007 |
Errores
| HTTP | Código | Significado |
|---|---|---|
401 | unauthorized | API key ausente o inválida. |
402 | insufficient_balance | El saldo no cubre el precio de la tarea. |
404 | unknown_type | El tipo de tarea no existe. |
429 | rate_limited | Demasiadas peticiones. Use el webhook en vez de sondear. |
Notas técnicas
Usted proporciona tres enteros —g, h y un módulo primo p— y recibe una respuesta JSON estructurada con la solución, los residuos reducidos y una ecuación de verificación cuando existe solución.
Qué pide el logaritmo discreto
Ese es el contrato de este endpoint: aritmética modular pura, sin heurísticas y sin llamadas de red.
Cómo encuentra x el paso enano, paso gigante
El método emplea del orden de la raíz cuadrada de p multiplicaciones y entradas de tabla, razón por la cual esta capacidad limita el módulo primo cerca de un billón: suficiente para tareas, recorridos de protocolos y pruebas de esfuerzo de subgrupos pequeños, pero acotado para que la memoria y la latencia sigan siendo predecibles en un Worker. Antes de buscar, el solucionador ejecuta una prueba de primalidad determinista de Miller–Rabin sobre p; si p es compuesto, la llamada falla con invalid_input en lugar de inventar un logaritmo en una estructura que no es el grupo multiplicativo del cuerpo primo.
Entradas, límites, precio y cuándo no hay solución
El precio de la API es una tarifa plana de $0.002 por solicitud correcta bajo la unidad de ítem; la validación fallida no se cobra.
Preguntas técnicas
¿Cómo resuelvo un logaritmo discreto con esta API?
Envíe por POST los enteros g, h y el primo p al endpoint del logaritmo discreto (o use el formulario gratuito del navegador). La respuesta incluye solved, el exponente x cuando existe, los residuos reducidos y una ecuación de verificación.
¿Cuánto cuesta la API?
La herramienta del navegador es gratuita. La API cobra $0.002 por solicitud correcta de su saldo prepago del KIT; la entrada no válida no se cobra. No se requiere suscripción.