Arithmétique modulo m

• Accueil
• Cryptographie
• Stéganographie
• Cryptanalyse
• Lexique

Définissons l'arithmétique modulo m: Z_m symbolise l'ensemble {0, ..., m-1} muni de deux opérations + et x. L'addition et la multiplication dans Z_m fonctionnent exactement comme l'addition et la multiplication usuelles, excepté le fait que tous les résultats sont réduits modulo m.
Supposons par exemple que l'on veuille calculer 11 x 13 dans Z₁₆. Comme entiers ordinaires, on a 11 x 13 = 143. Pour réduire 143 modulo 16, on fait une division euclidienne: 143 = 8 x 16 + 15, donc 143 mod 16 = 15, et, donc, 11 x 13 = 15 dans Z₁₆.

Ces définitions de l'addition et de la multiplication satisfont la plupart des règles familières en arithmétique. On rappelle la liste de ces propriétés sans les démontrer:

1. l'addition est interne: si a et b appartiennent à Z_m, alors a + b appartient à Z_m
2. l'addition est commutative: si a et b appartiennent à Z_m, alors a + b = b + a
3. l'addition est associative: si a, b et c appartiennent à Z_m, alors (a + b) + c = a + (b + c)
4. 0 est le neutre pour l'addition: si a appartient à Z_m, alors a + 0 = 0 + a = a
5. l'opposé de tout a appartenant à Z_m est m - a: a + (m - a) = (m - a) + a = 0 (sauf pour a = 0 qui est son propre opposé)

Puisque les opposés existent dans Z_m, on peut aussi faire des soustractions. On définit a - b dans Z_m comme étant a + m - b mod m. De manière équivalente, on peut calculer l'entier a - b et le réduire modulo m. Par exemple, pour calculer 11 - 18 dans Z₃₁, on peut évaluer 11 + 13 mod 31 = 24. On peut aussi retrancher 18 de 11, obtenir -7 et calculer -7 mod 31 = (-7 + 31) mod 31 = 24.

6. la multiplication est interne: si a et b appartiennent à Z_m, alors ab appartient à Z_m
7. la multiplication est commutative: si a et b appartiennent à Z_m, alors ab = ba
8. la multiplication est associative: si a, b et c appartiennent à Z_m, alors (ab)c = a(bc)
9. 1 est le neutre pour la multiplication: si a appartient à Z_m, alors a x 1 = 1 x a = a
10. la multiplication est distributive sur l'addition: si a, b et c appartiennent à Z_m, alors (a + b)c = ac + bc et a(b + c) = ab + ac

11. aⁿ mod m = (a mod m)ⁿ mod m

12. L'inverse modulo n de b est le nombre entier b^-1 tel que b·b^-1 mod n = 1. On peut le calculer avec l'algorithme d'Euclide étendu.

• Stinson Douglas, Cryptographie - Théorie et pratique, Vuibert Informatique, Paris, 2001, pp. 3-4
• Michel Van Caneghem, Congruences et théorème chinois des restes, février 2003

Didier Müller, 28.1.21