Calculateur pas de bébé-pas de géant de logarithmes discrets

Ce calculateur pas de bébé-pas de géant trouve un exposant non négatif x tel que g puissance x soit congru à h modulo n. Contrairement aux solveurs limités aux corps premiers, il traite aussi les modules composés et les bases non premières avec le module grâce à une réduction préalable. Le résultat fournit les résidus normalisés et une équation de contrôle lisible. Si la cible n’est pas atteignable depuis le générateur indiqué, la requête renvoie une erreur explicite plutôt qu’un résultat vide ambigu.

Décrivez précisément l’équation modulaire

Fournissez trois entiers : g désigne le générateur ou la base, h la cible et n le module. Le calculateur cherche un x non négatif vérifiant g^x congru à h modulo n. Les bases et cibles négatives sont acceptées puis normalisées dans l’intervalle standard allant de zéro à n moins un.

La réponse reprend ces valeurs normalisées afin que vous puissiez contrôler l’instance exacte, même si les données initiales sortaient de cet intervalle. Le module doit valoir au moins deux ; il peut être premier ou composé dans la limite publiée. L’exposant zéro est examiné en premier, selon la convention habituelle où g^0 vaut un modulo n.

Une cible congrue à un donne donc immédiatement x égal à zéro. Une réponse positive contient x, les opérandes normalisés, le nom de la méthode et une équation de vérification lisible. Elle convient aussi bien à un contrôle manuel qu’à une assertion automatisée sans reconstruire le texte dans chaque application cliente.

Comprenez les petits pas et les pas géants

Une recherche directe essaie les exposants successifs et peut demander un nombre de multiplications modulaires proportionnel au module. La méthode pas de bébé-pas de géant échange de la mémoire contre de la vitesse. Elle choisit une largeur proche de la racine carrée de l’espace de recherche, mémorise les petites puissances successives de la base, puis parcourt la cible par bonds de cette largeur.

Une égalité de résidus associe les deux indices et permet de retrouver l’exposant. La table et le nombre de bonds sont ainsi de l’ordre de la racine carrée de n. Cette réalisation est déterministe : aucun candidat n’est tiré au hasard, aucune graine, aucun service et aucune horloge n’interviennent.

Pour les entrées non premières entre elles, la variante étendue commence par retirer les diviseurs communs tout en conservant un décalage d’exposant et un multiplicateur. Si un diviseur rend la cible inaccessible, l’équation est rejetée immédiatement. Dès que la base réduite devient inversible, la recherche par table démarre et le décalage final est ajouté.

Le candidat obtenu est enfin vérifié séparément par exponentiation modulaire.

Limites et cas sans solution

Un logarithme discret n’existe pas toujours. Les puissances de g peuvent ne parcourir qu’une partie des résidus modulo n et laisser h hors de la suite engendrée. Ce choix est volontaire et facilite les chaînes où cette absence doit interrompre l’étape suivante : vous pouvez traiter le code normalisé sans rechercher de champ nul.

Les entiers incorrects, les champs manquants et un module hors limites produisent la même catégorie avec un message plus précis. Le coût de calcul augmente comme la racine carrée du module réduit, car l’algorithme crée une table en mémoire ; la borne empêche les allocations excessives et limite la durée. Employez des paramètres modestes pour l’enseignement, les vecteurs de test, les énigmes et le diagnostic.

Cet outil ne récupère pas les secrets de groupes cryptographiques réels, volontairement beaucoup plus grands.