Solveur de logarithme discret en ligne

Résoudre un logarithme discret pas à pas

Ce solveur en ligne détermine le plus petit exposant non négatif x tel que g^x est congru à h modulo p. Par exemple, avec les valeurs par défaut g=2, h=8 et p=13, le résultat est x=3 car 2^3 = 8, et 8 mod 13 = 8. La recherche commence à l'exposant 0 (valeur 1) et multiplie successivement par g modulo p jusqu'à trouver une correspondance ou épuiser les p essais.

Paramètres et fonctionnement

Les entrées g, h et p doivent être des entiers. Le module p est limité à l'intervalle [2, 1 000 000] pour garantir un temps de calcul raisonnable. La valeur h est normalisée modulo p, donc une valeur négative ou supérieure au module est comparée par son résidu. La recherche est exhaustive et s'arrête dès qu'un exposant correspond, ou après p vérifications si aucune solution n'existe.

Exemple concret

Entrez g=3, h=4, p=7. Le solveur teste x=0 (1 mod 7 = 1), x=1 (3 mod 7 = 3), x=2 (3*3=9 mod 7 = 2), x=3 (2*3=6 mod 7 = 6), x=4 (6*3=18 mod 7 = 4). Il trouve x=4 car 3^4 = 81 et 81 mod 7 = 4. Le résultat affiché est donc 4.

Limites et précautions

Cet outil est purement pédagogique : il effectue une recherche exhaustive en O(p) et ne convient pas aux modules cryptographiques réels (souvent de plusieurs centaines de chiffres). Il ne garantit pas que g génère le groupe multiplicatif, et avec des valeurs non premières entre elles, le cycle peut être plus court, mais la recherche bornée reste correcte. Les calculs sont effectués localement dans votre navigateur, sans envoi de données à un serveur ni utilisation d'IA.

Questions fréquentes

Que se passe-t-il si aucune solution n'existe ?

Si aucun exposant x entre 0 et p-1 ne satisfait la congruence, l'outil affiche un message indiquant qu'aucune solution n'a été trouvée. Cela peut arriver lorsque h n'est pas dans l'ensemble des puissances de g modulo p.

Pourquoi le module est-il limité à 1 000 000 ?

La recherche exhaustive teste jusqu'à p valeurs. Pour éviter de bloquer l'interface pendant de longues secondes, le module est plafonné à un million. Les modules cryptographiques réels sont beaucoup plus grands et rendraient le calcul impossible en pratique.

Puis-je utiliser des nombres négatifs pour h ?

Oui, h est automatiquement réduit modulo p. Par exemple, si p=13 et h=-5, le résidu est 8 (car -5 + 13 = 8), donc le solveur cherche une puissance de g qui donne 8 modulo 13.

Vérification rapide

• Les entiers saisis sont-ils valides (pas de texte, pas de décimales) ?
• Le module p est-il compris entre 2 et 1 000 000 ?
• Le résultat affiché est-il bien le plus petit exposant non négatif ?
• Avez-vous vérifié la congruence avec un calcul indépendant pour un usage important ?