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). |
Astuces
- 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.
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.