L'arithmetique modulaire est une arithmetique sur un cercle. Deux nombres sont congrus modulo n s'ils different d'un multiple de n. Une horloge fait de l'arithmetique modulo 12 : 10 heures apres 5 heures, il est 3 heures, pas 15. Cette idee simple est a la base de toute la cryptographie moderne, des fonctions de hachage, des codes correcteurs d'erreurs et d'une grande partie de la theorie des nombres.
Every row and column contains {0,1,2,3,4} exactly once. The five elements form a closed group under addition mod 5. Red: sums that wrap around (≥5).
| + | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 | 4 |
| 1 | 1 | 2 | 3 | 4 | 0 |
| 2 | 2 | 3 | 4 | 0 | 1 |
| 3 | 3 | 4 | 0 | 1 | 2 |
| 4 | 4 | 0 | 1 | 2 | 3 |
L'arithmetique modulaire definit la congruence : a est congru a b modulo n si n divise a-b. Gauss l'a systematisee en 1801. Elle est a la base de toute la cryptographie a cle publique moderne : le chiffrement RSA repose sur le petit theoreme de Fermat, qui enonce que a^(p-1) est congru a 1 modulo p pour tout premier p ne divisant pas a. Les fonctions de hachage utilisent des operations modulaires pour faire correspondre de grandes entrees a des sorties de taille fixe. Les entiers modulo n forment un anneau complet, et lorsque n est premier, un corps fini.