Comment j’ai travaillé : J’ai revu d’abord les bases à la lecture d’un livre de Simon Singh sur L’histoire des codes secrets aux éditions JC Lattès. J’ai parcouru un livre de terminale S Spécialité math des éditions belin paru en 2010 de 3 professeurs agrégés .J’ai demandé à un modèle d’IA de vous fabriquer l’horloge et j’ai trouvé l’exemple illustratif le plus parlant sur lequel j’ai basé toute ma pédagogie.
L’arithmétique modulo, parfois appelée l’arithmétique de l’horloge est un domaine riche en fonction à sens unique notamment lorsque l’on utilise l’exponentiation. Une fonction à sens unique donne un résultat que l’on peut très difficilement retrouver en inversant la fonction sur le plan computationnel.
L’arithmétique modulo est relativement simple, et nous l’utilisons tous les jours lorsque nous parlons de l’heure.
En effet dans l’arithmétique modulo les mathématiciens considèrent un ensemble fini de nombres arrangés en boucle, un peu comme les nombres sur une horloge.
1. Les mathématiques de l’horloge
Amusez sur cette horloge pour vous familiariser avec ce concept des mathématiques.
Sur cette horloge le modulo est 12. Cela représente le nombre total d’heures affichées sur une montre à aiguilles :
Exemple pratique :
Placez vous sur 10 h c’est l’état initial à laquelle j’ai mis l’horloge. J’ai rendez-vous à 2 heures de l’après midi , je vais réaliser l’opération 10 + 4 ≡ 2 (modulo 12)
le symbole ≡ désigne une relation de congruence et j’y reviendrai : Plutôt que égal on peut dire identique à d’après le standard Unicode de la table de caractères de la typographie Cambria Maths.
Autre exemple qui donne le même résultat :
si j’ajoute 16 heures je vais faire l’opération 10 + 16 ≡ 2 (modulo 12) il sera 2 heures du matin.
2. La division euclidienne : comprendre le calcul du reste
Pour comprendre le fonctionnement de l’arithmétique modulaire, il est indispensable de revenir sur une opération mathématique fondamentale : la division euclidienne.
Contrairement à une division décimale, qui peut produire un résultat avec une partie fractionnaire, la division euclidienne de deux nombres entiers permet d’obtenir deux valeurs entières : un quotient et un reste.
La division euclidienne repose sur la relation mathématique suivante :
a = b × q + r
Dans cette expression :
- a représente le dividende, c’est-à-dire le nombre à diviser.
- b représente le diviseur, qui doit être strictement positif.
- q représente le quotient entier.
- r représente le reste de la division.
Une condition fondamentale doit toujours être respectée :
0 ≤ r < b
Autrement dit, le reste doit être positif ou nul et strictement inférieur au diviseur. Pour un dividende et un diviseur donnés, il existe un unique couple d’entiers (q, r) qui satisfait ces conditions.
Calculer le reste avec notre horloge de 12 heures
Reprenons notre premier exemple.
Il est 10 heures du matin et nous ajoutons 4 heures :
10 + 4 = 14
Nous obtenons 14 heures, soit 2 heures de l’après-midi.
Pour retrouver cette valeur sur une horloge de 12 heures, nous devons effectuer la division euclidienne de 14 par 12.
Nous cherchons d’abord le plus grand multiple de 12 inférieur ou égal à 14.
Dans notre cas, il s’agit de :
12 × 1 = 12
Pour calculer le reste, nous soustrayons ce multiple de notre dividende
14 − 12 = 2
Nous pouvons donc écrire la division euclidienne :
14 = 12 × 1 + 2
Nous obtenons un quotient entier de 1 et un reste de 2.
Le quotient nous indique que nous avons effectué un tour complet de 12 heures, tandis que le reste correspond à la position finale sur le cadran.
L’opération modulo permet précisément d’obtenir ce reste :
14 mod 12 = 2
Ou, en reprenant notre addition initiale :
(10 + 4) mod 12 = 2
Nous retrouvons bien les 2 heures de l’après-midi.
2.1 Calculer le reste avec notre deuxième exemple
Imaginons maintenant qu’il soit toujours 10 heures du matin, mais que nous ajoutions cette fois 16 heures.
10 + 16 = 26
Nous obtenons 26 heures depuis le début de la journée initiale, ce qui correspond à 2 heures du matin le lendemain.
Effectuons maintenant la division euclidienne de 26 par 12.
Nous cherchons, comme précédemment, le plus grand multiple de 12 inférieur ou égal à 26.
Nous constatons que :
12 × 2 = 24
Calculons maintenant le reste :
26 − 24 = 2
La division euclidienne s’écrit alors :
26 = 12 × 2 + 2
Nous obtenons un quotient entier de 2 et un reste de 2.
Cette fois, le quotient indique deux cycles complets de 12 heures, mais le reste est toujours égal à 2.
Nous pouvons donc écrire :
26 mod 12 = 2
Ou encore :
(10 + 16) mod 12 = 2
Nous retrouvons exactement la même position sur le cadran de notre horloge, bien que 12 heures séparent les deux instants.
Une méthode générale pour calculer le reste
Le calcul d’un reste peut être généralisé à partir de la formule de la division euclidienne :
a = b × q + r
En isolant le reste r, nous obtenons :
r = a − b × q
Le quotient entier q peut être calculé à l’aide de la partie entière inférieure de la division a/b, également appelée fonction plancher :
q = ⌊a / b⌋
Nous pouvons donc écrire :
r = a − b × ⌊a / b⌋
Cette formule permet de calculer directement le reste d’une division euclidienne par un entier strictement positif.
Reprenons nos deux exemples.
Pour 14 divisé par 12 :
q = ⌊14 / 12⌋ = 1
r = 14 − (12 × 1) = 2
Pour 26 divisé par 12 :
q = ⌊26 / 12⌋ = 2
r = 26 − (12 × 2) = 2
Nous retrouvons bien le même reste dans les deux opérations.
Du reste de la division à l’arithmétique modulaire
Nos deux divisions euclidiennes donnent finalement :
14 = 12 × 1 + 2
26 = 12 × 2 + 2
Les quotients sont différents, mais les restes sont identiques.
C’est une observation fondamentale : deux nombres entiers différents peuvent avoir le même reste lorsqu’ils sont divisés par un même entier.
Dans notre exemple, 14 et 26 donnent tous les deux le reste 2 lorsqu’ils sont divisés par 12.
Cela nous permet d’écrire :
14 mod 12 = 26 mod 12 = 2
Cette propriété constitue le fondement de la notion de congruence en arithmétique modulaire.
En effet, puisque 14 et 26 possèdent le même reste dans leur division euclidienne par 12, nous pouvons affirmer qu’ils sont congrus modulo 12 :
14 ≡ 26 ≡ 2 (mod 12)
Ainsi, la division euclidienne permet de calculer le reste, tandis que la congruence permet d’établir une relation mathématique entre les nombres qui partagent ce même reste.
3. La congruence en arithmétique modulaire
En arithmétique modulaire, la notion de congruence permet d’établir une relation entre deux nombres entiers qui possèdent le même reste lorsqu’ils sont divisés par un même entier strictement positif, appelé module.
Cette relation s’écrit :
14 ≡ 26 ≡ 2 (mod 12)
Le symbole ≡, constitué de trois barres horizontales, désigne ici une relation de congruence. Il ne faut pas le confondre avec le symbole d’égalité =.
En effet, les nombres 14, 26 et 2 ne sont pas égaux dans l’ensemble des entiers, mais ils appartiennent à une même classe de congruence modulo 12.
Il convient donc de distinguer les deux notations suivantes :
- (10 + 4) mod 12 = 2 : nous effectuons une opération modulo qui donne le reste de la division euclidienne.
- 10 + 4 ≡ 2 (mod 12) : nous exprimons une relation de congruence entre deux nombres.
De la même manière :
- (10 + 16) mod 12 = 2
- 10 + 16 ≡ 2 (mod 12)
La première notation représente un calcul, tandis que la seconde exprime une propriété mathématique.
La définition mathématique de la congruence
Deux entiers a et b sont congrus modulo n si et seulement si leur différence est divisible par n.
Autrement dit :
a ≡ b (mod n) ⇔ n divise (a − b)
Cela signifie qu’il existe un entier relatif k tel que :
a − b = k × n
Reprenons les résultats de notre horloge :
14 − 2 = 12 = 1 × 12
26 − 2 = 24 = 2 × 12
26 − 14 = 12 = 1 × 12
Dans chacun de ces calculs, la différence est un multiple de 12.
Nous pouvons donc écrire :
14 ≡ 26 ≡ 2 (mod 12)
Cette propriété explique pourquoi les trois nombres sont équivalents du point de vue de l’arithmétique modulo 12.
Sur une horloge à 12 heures, ils correspondent tous à la même position de l’aiguille des heures.
Cependant, une horloge à 12 heures ne suffit pas, à elle seule, à déterminer s’il est 2 heures du matin ou 2 heures de l’après-midi. Cette distinction nécessite une information supplémentaire, comme l’indication AM/PM ou l’utilisation du format de 24 heures.
3.1 Les classes de congruence
Cette propriété permet de regrouper les nombres entiers en classes d’équivalence.
Dans une arithmétique modulo 12, tous les entiers peuvent être répartis dans douze classes distinctes, représentées par les restes allant de 0 à 11.
Par exemple, la classe de congruence de 2 modulo 12 contient les entiers :
…, −22, −10, 2, 14, 26, 38, 50, …
Tous ces entiers sont congrus entre eux modulo 12, car la différence de deux de ces nombres est toujours un multiple de 12.
Nous pouvons les représenter sous la forme générale :
2 + 12k, avec k ∈ ℤ.
k désigne un entier relatif quelconque qui permet de parcourir tous les nombres de cette classe.
En faisant varier (k), nous obtenons :
| Valeur de (k) | Calcul (2+12k) | Résultat |
|---|---|---|
| −3 | (2+12(-3) | −34 |
| −2 | (2+12(-2) | −22 |
| −1 | (2+12(-1) | −10 |
| 0 | (2+12(0) | 2 |
| 1 | (2+12(1) | 14 |
| 2 | (2+12(2) | 26 |
| 3 | (2+12(3) | 38 |
ℤ désigne les entiers relatifs dans la théorie des ensembles (cliquez sur ce lien) c’est à dire tous les nombres négatifs et les entiers naturels notés ℕ .
L’ensemble des classes de congruence modulo 12 est désigné en mathématiques par la notation :
ℤ/12ℤ
Plus généralement, l’ensemble des classes d’entiers modulo n se note :
ℤ/nℤ
Cet ensemble comporte exactement n classes de congruence distinctes lorsque n est un entier strictement positif.
Pourquoi la congruence est-elle importante ?
La congruence constitue un outil fondamental en théorie des nombres, car elle permet de travailler avec des classes de nombres plutôt qu’avec chaque entier individuellement.
Elle possède également une propriété essentielle : elle est compatible avec l’addition et la multiplication.
Par exemple, si deux nombres sont congrus modulo n, nous pouvons leur ajouter un même entier ou les multiplier par un même entier sans perdre cette relation de congruence.
Cette propriété permet de simplifier considérablement les calculs faisant intervenir de très grands nombres.
Elle joue notamment un rôle important dans l’exponentiation modulaire, utilisée en cryptographie asymétrique, mais également dans les calculs sur les mots binaires de taille fixe employés par certains algorithmes de hachage cryptographique.
Ainsi, notre simple horloge de 12 heures illustre une notion mathématique fondamentale dont les applications dépassent largement la mesure du temps.
4. Arithmétique classique versus arithmétique modulo
4.1 L’exponentiation modulaire
Les fonctions effectuées en arithmétique modulo tendent à se comporter de manière erratique, ce qui les transforme parfois en fonction à sens unique sur le plan computationnel.
Cela devient évident lorsqu’une fonction simple en arithmétique normale est comparée à la fonction en arithmétique modulo.
Dans la première la fonction à double sens sera aisément inversible. Dans la seconde elle sera à sens unique et difficilement inversible.
Comparaison entre l’arithmétique ordinaire et l’arithmétique modulo pour 3^x et 3^x (mod 7) en fonction des valeurs de x.
Prenons par exemple 3^3 = 27, j’ai utilisé une fonction exponentielle. Maintenant je prends la réciproque de cette fonction : le logarithme que je vous ai introduit dans un autre article :
En arithmétique ordinaire plus la valeur croit, plus le résultat croit. Si on nous donnait le résultat de l’opération il serait facile de revenir en arrière et de déduire le nombre d’origine.
En arithmétique modulo cette même fonction ne se comporte pas si raisonnablement.
Souvent le seul moyen pour inverser une fonction est de constituer une table même si il existe des algorithmes spécialisés, comme Baby-step Giant-step ou l’algorithme de Pollard.
Si établir une table est un peu fastidieux lorsqu’on travaille sur d’assez petits nombres cela devient extrêmement pénible sur une fonction comme
L’exponentiation modulaire consiste à effectuer cette opération, puis à conserver uniquement le reste de la division euclidienne par un nombre appelé module.
Choisissons le module 23 :
Nous savons que :
Effectuons la division euclidienne de 27 par 23 :
Le reste de cette division est égal à 4.
Nous obtenons donc :
Nous pouvons également écrire cette opération sous la forme d’une congruence :
Dans cet exemple, nous connaissons la base (3), l’exposant (3) et le module (23). Nous cherchons simplement à calculer le résultat.
Il s’agit d’une exponentiation modulaire.
4.1 Le problème du logarithme discret
Intéressons-nous maintenant au problème inverse.
En arithmétique classique, nous avons vu que nous pouvons inverser une exponentiation à l’aide d’une fonction logarithme.
Imaginons maintenant que nous connaissions uniquement la base 3, le module 23 et le résultat 4, mais plus l’exposant.
Nous devons alors résoudre l’équation suivante :
Quel exposant faut-il attribuer à 3 pour obtenir un reste de 4 après la division par 23 ?
C’est ce que les mathématiciens appellent le problème du logarithme discret.
Avec de petits nombres, nous pouvons retrouver l’exposant en effectuant plusieurs essais :
Nous constatons que l’exposant 3 permet effectivement d’obtenir le résultat recherché.
Cependant, une particularité importante apparaît : plusieurs exposants peuvent produire exactement le même résultat en arithmétique modulaire.
En effet :
Les puissances de 3 se répètent donc avec une période de 11 modulo 23. La période d’un nombre est définie par le plus petit exposant entier strictement positif pour un reste = 1
Ainsi :
Nous obtenons également :
Les exposants 3, 14 et 25 donnent le même résultat.
4.2 Pourquoi le logarithme discret est-il important en cryptographie ?
Nous venons de mettre en évidence une différence fondamentale entre deux problèmes mathématiques.
Premier problème : l’exponentiation modulaire.
Nous connaissons la base, l’exposant et le module. Nous devons calculer le résultat.
Deuxième problème : le logarithme discret.
Nous connaissons la base, le module et le résultat, mais nous devons retrouver l’exposant.
Dans notre exemple, la résolution est simple puisque les nombres sont petits.
Mais lorsque nous travaillons avec des nombres premiers de très grande taille et des paramètres mathématiques appropriés, le problème devient beaucoup plus difficile sur le plan informatique.
L’exponentiation modulaire reste relativement rapide à effectuer grâce à des algorithmes efficaces.
En revanche, retrouver l’exposant à partir du résultat peut nécessiter une quantité considérable de calculs, même avec des méthodes spécialisées.
Il faut néanmoins préciser que tous les problèmes de logarithme discret ne sont pas difficiles. Leur complexité dépend notamment du groupe mathématique utilisé, de sa taille et des algorithmes disponibles.
Cette différence de difficulté entre le calcul direct et la résolution du problème inverse constitue l’un des fondements mathématiques de plusieurs mécanismes de cryptographie à clé publique.
5. Une application : le protocole Diffie-Hellman
Cette propriété est notamment exploitée dans le protocole Diffie-Hellman, présenté en 1976 par Whitfield Diffie et Martin Hellman.
Ce protocole permet à deux correspondants d’établir un secret partagé en échangeant des informations sur un canal de communication public, sans transmettre directement ce secret.
Son fonctionnement repose sur des exponentiations modulaires et sur la difficulté de certains problèmes mathématiques associés, notamment le logarithme discret.