Arithmétique modulaire
From Isiwiki
Complément au cours Outils formels
Contents |
[edit] Définitions
En arithmétique modulo k on considère que deux nombres sont équivalents si le reste de leurs divisions par k sont les même, ou, ce qui revient au même, si leur différence est un multiple de k. Exemple. Si k=5 (on dit alors qu'on calcule dans Z/5Z, ou modulo 5) on a
12 == 17 car 12:5 = 2 reste 2 et 17:5 = 3 reste 2
En fait il n'y a que 5 classes de nombres différents dans les entiers modulo 5 : ceux dont le reste de la division par 5 vaut 0, ceux dont le reste vaut 1, ..., ceux dont le reste vaut 4. On parle des classes de restes modulo 5.
Dans les entiers modulo k il y a k classes de restes, donc tout nombre est équivalent soit à 0, soit à 1, ..., soit à k-1.
[edit] Opérations
[edit] Addition et multiplication
Les opérations d'addition et de multiplicaiton fonctionnent comme prévu car
Si x == a et y == b alors (x+y) == (a+b)
Par exemple, dans Z/5Z, 12 + 16 = 28 == 3, mais comme 12 == 2 et 16 == 1 on peut aussi faire 2+1 = 3, c'est plus simple.
Idem pour la multiplication : 219 × 111 = 243009 == 4, comme 219 == 4 et 111 == 1 il suffit de faire 4 × 1 = 4.
[edit] Inverses (soustraction et division)
Tout nombre x possède un inverse pour l'addition, c'est à dire un nombre x' tels que x + x' = 0. Par exemple, l'inverse de 1 est 4, l'inverse de 2 est 3, ... (modulo 5). En d'autres termes, -1 = 4, -2 = 3, -3 = 2, -4 = 1.
Pour la multiplication il y a un petit hic
Si on travaille dans les entiers modulo k et que k n'est pas un nombre premier on a deux ennuuis :
- certain nombres non nuls n'ont pas d'inverse pour la multiplication
- certains nombres sont des diviseurs de 0 (c'est très gênant pour résoudre des équations)
Exemple. Dans les entiers modulo 6, il n'y a pas de nombre z tel que 2 × z == 1, 2 n'a pas d'inverse pour la multipication. De plus, 2 × 3 = 6 == 0, 2 est un diviseur de 0.
Par contre, si k est un nombre premier (sans diviseurs) tout va bien.
Par exemple, dans les entiers modulo 5 on a 1 × 1 = 1, 2 × 3 = 6 == 1, 3 × 2 = 6 == 1, 4 × 4 = 16 == 1. Autrement dit 1/1 = 1, 1/2 = 3, 1/3 = 2, 1/4 = 4.
tout le monde (sauf 0) a un inverse. On peut donc utiliser les quatre opération habituelles : soustraire c'est ajouter l'inverse pour l'addition, diviser c'est multiplier par l'inverse pour la multiplication.
[edit] Résolution d'équations
On peut résoudre des équations de la manière haibtuelle :
3x + 2 = 4 (modulo 5) donc, 3x = 4+3 == 2 (modulo 5) car -2 = 3 donc, x = 2 × 2 (modulo 5) car 1/3 = 2 et donc, x = 4
[edit] Mais à quoi ça sert ?
[edit] La preuve par 9
Pour se prémunir contre ceraines erreurs de calcul on peut procéder ainsi :
On fait le calcul voulu, disons A × B, et on trouve C comme résultat.
Le calcul doit aussi être vrai modulo 9, on vérifie que A modulo 9 × B modulo 9 = C modulo 9.
Ce procédé est intéressant pour calculer A modulo 9 il suffit d'additionner les chiffres de A (et les chiffres de la somme si celle-ci est > 9).
Exemple. On calcule 863 × 1174 = 1023162.
Vérifions :
- 863 modulo 9 : 8+6+3 = 17, 1+7 = 8
- 1174 modulo 9 = 1+1+7+4 = 13, 1+3 = 4
- 1013162 modulo 9 = ... = 6
- on a 8 × 4 = 32 == 5 modulo 9, erreur
Attention! Cette technique ne permet pas de détecter toutes les erreurs.
[edit] Sommes de vérification
On veut transmettre un message composé de chiffres (p.ex. un numéro de téléphone) et détecter certaines erreurs de transmission.
La technique consiste à calculer un chiffre de contrôle qu'on ajoute à la fin du message. Le récepteur fait le même calcul et vérifie qu'il obtient bien le même chiffre. L'un des calculs le plus simples consiste, comme dans l'exemple précédent, à faire la somme des chiffres (et la somme des chiffres de la somme si nécessaire, et ainsi de suite), on obtient de cette manière le reste modulo 9 du nombre correspondant au message.
Exemple. Pour le message 684829356394 on calcule 6+8+4+8+2+9+3+5+6+3+9+4 = 67, 6+7 = 13, 1+3 = 4 et on transmet 6848293563944.
Cette technique permet de détecter toute erreur sur un chiffre (car elle change forcément le modulo 9). Par contre certaines erreurs sur 2 chiffres ne seront pas détectées, p.ex. si l'un est augmenté de 3 et l'autre diminué de 3.
Dans les codes ISBN, qui identifient les livres, il y a un chiffre de contrôle dont le calcul est basé sur les restes modulo 11. Voir l'article de Wikipédia à ce sujet [1]
[edit] Cryptograhie
Supposons que Alice et Bob ne peuvent se parler que via un canal public et qu'ils ont besoin de créer un secret qu'eux seuls connaissent. Une méthode remarquablement simple a été trouvée par Diffie et Hellman pour réaliser cette tâche à première vue impossible. La méthode utilise l'arithmétique modulaire.
Voir [2]
Le fameux algorithme de cryptage à clé publique RSA est également basé sur le calcul dans Z/pZ (avec p très grand).
