Calculateur d'arithmétique modulaire (calculateur de mod)
Un calculateur d'arithmétique modulaire proposant 4 modes : mod de base, addition/soustraction/multiplication modulaire, exponentiation modulaire (exponentiation rapide par élévations au carré successives) et inverse modulaire (algorithme d'Euclide étendu). Calcule avec précision le mod des nombres négatifs et les exposants énormes grâce à BigInt.
Propriétés de base de l'arithmétique modulaire
| Propriété | Description |
|---|---|
| (a + b) mod n = ((a mod n) + (b mod n)) mod n | Que l'on prenne le mod avant ou après l'addition, le résultat est exactement le même. |
| (a − b) mod n = ((a mod n) − (b mod n) + n) mod n | Comme la soustraction peut donner un résultat négatif, ajouter n à la fin puis reprendre le mod n permet de ramener le résultat dans l'intervalle [0, n). |
| (a × b) mod n = ((a mod n) × (b mod n)) mod n | Comme pour l'addition, prendre le mod en cours de multiplication ne change pas le résultat final. Cette propriété est à la base du calcul rapide de l'exponentiation (élévation au carré successive). |
| a et n sont premiers entre eux ⇔ un inverse de a modulo n existe | Ce n'est que lorsque l'algorithme d'Euclide étendu donne gcd(a, n) = 1 qu'il existe un x (l'inverse) satisfaisant a × x ≡ 1 (mod n). |
Qu'est-ce que l'arithmétique modulaire (calcul de mod) ?
L'arithmétique modulaire, aussi appelée congruence, est une opération qui ne s'intéresse qu'au reste de la division d'un nombre par un entier positif appelé module. Lorsque deux entiers a et b donnent le même reste dans une division par un même module n, on dit que « a et b sont congrus modulo n », ce que l'on note a ≡ b (mod n). Cet outil regroupe, en 4 modes, les calculs les plus courants liés à la congruence : « mod de base », « addition/soustraction/multiplication », « exponentiation » et « inverse ».
Tous les calculs internes reposent sur le type BigInt natif de JavaScript, ce qui permet d'obtenir des résultats exacts, sans erreur d'arrondi, même pour des exposants comptant plusieurs centaines de chiffres ou pour des additions, soustractions et multiplications portant sur de très grands entiers. Les nombres négatifs sont également acceptés : ils sont normalisés selon la définition mathématique de la congruence (le résultat se situe toujours entre 0 inclus et le module exclu), ce qui évite les surprises liées aux différences de comportement de l'opérateur de reste selon les langages de programmation.
Comment utiliser le calculateur d'arithmétique modulaire
- Choisissez un mode Sélectionnez le type de calcul souhaité parmi les quatre modes proposés : « mod de base », « addition/soustraction/multiplication », « exponentiation » et « inverse ».
- Saisissez les entiers Selon le mode choisi, renseignez a, b et le module n, ou bien la base et l'exposant. Les entiers négatifs peuvent être saisis directement.
- Choisissez un opérateur (mode addition/soustraction/multiplication uniquement) Sélectionnez l'addition, la soustraction ou la multiplication dans le menu déroulant prévu à cet effet.
- Consultez le résultat Le calcul se met à jour automatiquement à chaque saisie, et la formule ainsi que le résultat s'affichent. Si aucun inverse n'existe, un message l'indiquant apparaît à la place du résultat.
- Recommencez la saisie Le bouton « Effacer » permet de vider les champs de saisie de tous les modes en une seule fois.
Astuces pour en tirer le meilleur parti
- Le comportement du mod sur les nombres négatifs varie selon les langages de programmation. Cet outil suit la définition mathématique (le résultat est toujours compris entre 0 et n − 1), donc -7 mod 3 vaut 2, et non -1.
- Le mode d'exponentiation utilise l'élévation au carré successive : il renvoie donc un résultat instantané même lorsque l'exposant compte plusieurs centaines de chiffres. Le même algorithme est utilisé lors du chiffrement et du déchiffrement RSA.
- L'heure d'une horloge est un exemple familier d'arithmétique modulaire : convertir "15 h" au format 12 heures donne 15 mod 12 = 3 heures.
- Le mode inverse fonctionne dès lors que a et n sont premiers entre eux (leur plus grand commun diviseur vaut 1), même si n n'est pas premier.
- En programmation compétitive, il est fréquent que les énoncés demandent une réponse modulo un grand nombre premier comme 1 000 000 007, plutôt que le nombre brut, gigantesque. Le mode d'exponentiation de cet outil est pratique pour vérifier ce type de calcul à la main.
Situations dans lesquelles l'arithmétique modulaire est utile
Comprendre les algorithmes de chiffrement à clé publique
Le chiffrement et le déchiffrement en RSA reposent entièrement sur le calcul du reste d'une puissance d'un très grand nombre modulo n. Le mode exponentiation permet de constater concrètement la rapidité de l'élévation au carré successive, même avec un exposant et un module de grande taille.
Explorer les principes de conception des fonctions de hachage
De nombreuses fonctions de hachage utilisent en interne des opérations modulaires pour ramener une valeur dans un intervalle borné. Le mode addition/soustraction/multiplication permet de suivre pas à pas l'évolution du reste à chaque étape intermédiaire.
Vérifier le fonctionnement des clés de contrôle
Les clés de contrôle des numéros ISBN, des numéros de carte bancaire ou des numéros de compte se calculent généralement à partir du reste d'une somme pondérée des chiffres, divisée par un module. Le mode mod de base permet de reproduire ce calcul à la main pour le vérifier.
Effectuer des calculs de cycles liés au calendrier
Des questions à caractère cyclique comme « quel jour de la semaine tombera dans n jours ? » ou « selon quel cycle les années bissextiles reviennent-elles ? » se formulent naturellement sous forme de congruences modulo 7 ou modulo 4.
Vérifier une réponse en programmation compétitive
Pour les énoncés fréquents demandant « le reste de la division de la réponse par 1 000 000 007 », les modes exponentiation et addition/soustraction/multiplication permettent de contrôler que le résultat produit par son propre code est correct.
Glossaire de l'arithmétique modulaire
- Congruence
- Une relation de la forme a ≡ b (mod n), qui exprime que a et b ont le même reste dans une division par n. Le symbole « ≡ » est utilisé plutôt que « = » car ce n'est pas la valeur elle-même qui est égale, mais seulement le reste.
- Module
- Le nombre par lequel on divise. Cet outil n'accepte que des entiers supérieurs ou égaux à 1 pour cette valeur. Changer de module modifie la relation de congruence, même pour un même nombre de départ.
- Opération modulo (reste)
- Le calcul effectif du reste de la division d'un nombre par le module. Selon la définition mathématique, le résultat se situe toujours entre 0 inclus et le module exclu.
- Inverse modulaire
- Un entier x tel que a × x ≡ 1 (mod n). Il permet, dans l'univers de l'arithmétique modulaire où la division n'est pas directement définie, d'obtenir un effet équivalent à celui d'une division en multipliant par cet inverse.
- Nombres premiers entre eux
- Deux entiers dont le plus grand commun diviseur vaut 1. Ce n'est que lorsque a et n sont premiers entre eux qu'un inverse de a modulo n existe.
- Algorithme d'Euclide étendu
- Un algorithme qui calcule non seulement le plus grand commun diviseur de deux entiers, mais aussi un couple d'entiers (x, y) satisfaisant a × x + n × y = pgcd(a, n). Il est utilisé pour le calcul effectué en mode inverse.
- Élévation au carré successive (exponentiation rapide)
- Un algorithme qui décompose l'exposant en écriture binaire et multiplie le résultat par la base élevée au carré à chaque étape correspondant à un chiffre binaire à 1, ce qui permet de calculer une puissance avec un nombre de multiplications proportionnel au nombre de chiffres de l'exposant. C'est cette technique qui est employée par le mode exponentiation.
- Exponentiation modulaire
- Le calcul du reste de la division d'une puissance d'un nombre par un module. C'est l'opération centrale du chiffrement et du déchiffrement en RSA, et elle correspond au mode « exponentiation » de cet outil.
Questions fréquentes
Anecdote — l'« arithmétique de l'horloge » derrière la cryptographie moderne
L'arithmétique modulaire (congruence) est souvent appelée « arithmétique de l'horloge » (clock arithmetic). Sur une horloge à 12 heures, 13 h est traité comme « identique » à 1 h — c'est exactement la congruence 13 ≡ 1 (mod 12), une idée qui ne s'intéresse qu'au reste de la division d'un nombre par un module (ici 12). Le mathématicien allemand Carl Friedrich Gauss a systématisé la notation « ≡ » de la congruence dans son ouvrage de 1801, Disquisitiones Arithmeticae, faisant de cette idée un outil standard des mathématiques modernes.
Cette opération d'apparence simple soutient les fondations de la sécurité moderne d'Internet. Dans les systèmes à clé publique comme RSA, l'« exponentiation modulaire » — calculer la puissance d'un nombre énorme puis en prendre le reste modulo n — est l'opération centrale du chiffrement et du déchiffrement. L'exposant et le module pouvant chacun compter plusieurs centaines de chiffres, calculer naïvement la puissance complète avant d'en prendre le reste ferait exploser le volume de calcul. L'élévation au carré successive ne nécessite en revanche qu'un nombre de multiplications proportionnel au nombre de chiffres de l'exposant, ce qui la rend praticable.
Le calcul d'inverses modulaires par l'algorithme d'Euclide étendu est lui aussi une technique fondamentale utilisée dans de nombreux domaines de l'informatique, de la cryptographie à la théorie des codes en passant par la conception de fonctions de hachage. Le fait qu'une « arithmétique vieille de plus de 2 000 ans » et une « technologie de sécurité de pointe » reposent sur le même socle mathématique illustre de façon frappante l'universalité de la théorie des nombres.