Solveur de logarithme discret
Demandez quelle puissance de 2 donne 5 modulo 13 et vous obtenez 9, car 2^9 ≡ 5 (mod 13). Saisissez une base, une cible et un module premier pour trouver le plus petit exposant, avec une égalité vérifiable. Gratuit dans votre navigateur.
- Gratuit
- Fonctionne dans votre navigateur
- Sans inscription
- Vos données restent sur votre appareil
Lancer gratuitement
Exemple résolu
- G
- 2
- H
- 5
- Puissance (W)
- 13
- X
- 9
- Équation
- 2^9 ≡ 5 (mod 13)
Le problème du logarithme discret cherche un entier x tel qu'une base donnée g élevée à x soit congrue à une cible h modulo un premier p. Il fonde l'échange de clés Diffie–Hellman, le chiffrement ElGamal et de nombreux exercices de manuel en cryptographie algébrique. Cette capacité met en œuvre l'algorithme classique baby-step giant-step : une recherche déterministe en temps racine carrée qui, soit récupère le plus petit exposant non négatif, soit prouve que h n'est pas une puissance de g dans le groupe multiplicatif modulo p.
Ce que demande le logarithme discret
Étant donné des entiers g, h et un premier p, le logarithme discret de h en base g modulo p est tout entier x satisfaisant g à la puissance x congru à h modulo p. Lorsqu'une solution existe, le plus petit représentant non négatif dans l'intervalle zéro à p moins deux est unique une fois cet intervalle fixé, et c'est la valeur que renvoie cet outil.
Contrairement aux logarithmes réels ordinaires, il n'existe pas de formule élémentaire en forme fermée qui fonctionne pour des premiers arbitraires ; la difficulté de récupérer x pour de grands premiers soigneusement choisis est précisément ce qui rend utile la cryptographie à logarithme discret. Dans l'enseignement et les expériences à petits paramètres, il faut cependant un solveur correct et inspectable : un qui valide l'hypothèse de primalité, réduit les entrées dans le système canonique de résidus, cherche systématiquement, et soit affiche un exposant vérifiable, soit indique clairement qu'aucune solution n'existe.
Comment baby-step giant-step trouve x
Baby-step giant-step réécrit l'exposant inconnu sous la forme x égale i fois m plus j, où m vaut à peu près la racine carrée de l'ordre du groupe p moins un, et où i et j varient tous deux de zéro à m. L'algorithme stocke d'abord chaque valeur bébé g puissance j modulo p dans une table de hachage indexée par résidu, puis parcourt les pas de géant en multipliant à répétition la cible par l'inverse modulaire de g puissance m, en cherchant chaque résidu intermédiaire dans la table.
Une correspondance donne à la fois i et j, et donc x. Les bases et cibles hors de zéro à p moins un sont réduites modulo p, et la réponse renvoie les g, h et p réduits pour que les appelants auditent l'instance exacte qui a été résolue.
Entrées, limites, tarification et absence de solution
Les champs requis sont g (base), h (résidu cible) et p (module premier). Les chaînes de chiffres sont acceptées pour de grands entiers dans la limite du module. Si h n'est pas dans le sous-groupe cyclique engendré par g modulo p — par exemple quand g n'engendre qu'un sous-groupe propre et que h se trouve en dehors — le solveur renvoie solved false avec un exposant null et un message explicatif au lieu de fabriquer un x erroné.
Ce résultat est un calcul réussi, et non une erreur client, car l'entrée était bien formée et la réponse mathématique est qu'aucun logarithme n'existe. Les erreurs client couvrent les champs manquants, les non-entiers, les modules hors de la plage autorisée et un p composé. L'outil du navigateur exécute la même bibliothèque gratuitement sans compte.
Utilisez le résultat pour vérifier des devoirs, générer des tests à réponse connue pour des bibliothèques cryptographiques, ou explorer l'appartenance à un sous-groupe avant de passer à l'échelle des paramètres dans une vraie conception de protocole.
Cas d’usage
Vérification de devoirs et d'examens
Étudiants et enseignants vérifient des exercices de logarithme discret tels que 2^x ≡ 5 (mod 13) et reçoivent à la fois l'exposant et une congruence imprimable pour le corrigé.
Tests à réponse connue pour du code cryptographique
Les auteurs de bibliothèques alimentent de petites instances de corps premier dans l'intégration continue pour que exponentiation modulaire et inverse restent cohérents avec une référence BSGS indépendante.
Expériences d'appartenance à un sous-groupe
Les chercheurs essaient des bases et des cibles candidates modulo un petit premier pour voir si h appartient au sous-groupe engendré par g avant de passer à des paramètres de taille de production.
Questions fréquentes
Quel algorithme utilisez-vous ?
Baby-step giant-step (Shanks). Il trouve le plus petit x non négatif tel que g^x ≡ h (mod p) en environ O(√p) temps et mémoire, après un test de primalité déterministe sur p.
Que se passe-t-il si p n'est pas premier ?
Cet outil définit le logarithme discret dans le groupe multiplicatif d'un corps premier et ne travaillera pas en silence modulo un composé.
Et s'il n'existe aucun exposant ?
Vous obtenez solved: false et x: null avec un court message. C'est un résultat mathématique valable (h n'est pas une puissance de g mod p), pas une erreur de facturation ou de validation.
Comment résoudre 2^x ≡ 5 (mod 13) ?
Saisissez 2 comme base, 5 comme cible et 13 comme module premier. La réponse est 9 : 2 élevé à la puissance neuf, divisé par 13, laisse un reste de 5, et aucun exposant plus petit n'y parvient.
Jusqu'où peut aller le module premier ?
Jusqu'à environ mille milliards. Cela couvre les devoirs, les démonstrations de protocoles et les petites expériences avec une réponse rapide ; ce n'est pas prévu pour les très grands nombres premiers du chiffrement réel.
Outils associés
Pour les développeurs — accès API
Tout sur cette page est disponible par programmation. Cette section s'adresse aux équipes qui veulent l'intégrer à leurs systèmes ; les autres peuvent simplement utiliser l'outil ci-dessus.
Endpoint
Authentification par jeton Bearer : un seul POST met la tâche en file d’attente, et le résultat vous parvient par webhook ou lien signé.
Appeler depuis votre 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)Exemple de requête
{
"g": 2,
"h": 5,
"p": 13
}Exemple de réponse
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.discrete_log",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}L’API est asynchrone : chaque appel renvoie un task_id immédiatement, puis vous interrogez l’état à raison d’une requête par seconde.
Tarifs
Le prix est publié, sans tokens ni crédits. Une tâche qui échoue n’est pas facturée.
Limites
max_p | 1000000000007 |
Erreurs
| HTTP | Code | Signification |
|---|---|---|
401 | unauthorized | Clé API absente ou invalide : vérifiez l’en-tête Authorization. |
402 | insufficient_balance | Solde insuffisant : rechargez votre compte pour lancer cette tâche. |
404 | unknown_type | Type de tâche inconnu : vérifiez le champ type de votre requête. |
429 | rate_limited | Trop de requêtes : ralentissez la cadence, puis réessayez. |
Notes techniques
Vous fournissez trois entiers — g, h et un module premier p — et recevez une réponse JSON structurée avec la solution, les résidus réduits et une équation de vérification lorsqu'une solution existe.
Ce que demande le logarithme discret
Tel est le contrat de cet endpoint : de la pure arithmétique modulaire, aucune heuristique et aucune requête réseau.
Comment baby-step giant-step trouve x
La méthode utilise de l'ordre de racine carrée de p multiplications et entrées de table, raison pour laquelle cette capacité plafonne le module premier près de mille milliards : assez grand pour les devoirs, les démonstrations de protocole et les tests de charge de petits sous-groupes, mais borné pour que mémoire et latence restent prévisibles sur un Worker. Avant la recherche, le solveur exécute un test de primalité déterministe de Miller–Rabin sur p ; si p est composé, l'appel échoue avec invalid_input plutôt que d'inventer un logarithme dans une structure qui n'est pas le groupe multiplicatif du corps premier.
Entrées, limites, tarification et absence de solution
La tarification de l'API est de $0.002 par requête réussie sous l'unité item ; une validation échouée n'est pas facturée.
Questions techniques
Comment résoudre un logarithme discret avec cette API ?
POSTez les entiers g, h et le premier p vers l'endpoint de logarithme discret (ou utilisez le formulaire gratuit du navigateur). La réponse inclut solved, l'exposant x lorsqu'il existe, les résidus réduits et une équation de vérification.
Combien coûte l'API ?
L'outil du navigateur est gratuit. L'API facture $0.002 par requête réussie sur votre solde KIT prépayé ; une entrée invalide n'est pas facturée. Aucun abonnement n'est requis.