Approfondissements de lycée/Arithmétique modulaire approfondie

Un livre de Wikilivres.
Sauter à la navigation Sauter à la recherche

Approfondissements de lycée

Introduction[modifier | modifier le wikicode]

Les mathématiques sont la reine des sciences et la théorie des nombres est la reine des mathématiques. -- Carl Friedrich Gauss 1777 - 1855

Dans la section Nombres premiers et arithmétique modulaire, nous avons vu les propriétés élémentaires d'un nombre premier et sa relation avec l'arithmétique modulaire. Pour la plus grande partie, notre attention a été restreinte à l'arithmétique mod p, où p est un nombre premier.

Dans ce chapitre, nous démarrons en discutant certains résultats plus élémentaires dans l'arithmétique modulo un nombre premier p, puis en se déplaçant sur la discussion de ces résultats modulo mm est un nombre composé. En particulier, nous examinerons de plus près le Théorème des restes chinois (TRC), et comment il nous permet de casser l'arithmétique modulo m en composants. A partir de ce point de vue, le TRC est un outils extrêmement puissant qui peut nous aider à débloquer beaucoup de secrets de l'arithmétique modulaire (avec une relative facilité).

Enfin, nous introduirons l'idée d'un groupe abélien à travers la multiplication dans l'arithmétique modulaire et nous discuterons sur le problème du logarithme discret qui sous-tend un des plus importants systèmes cryptographiques connus actuellement.

Connaissance supposée Dans ce chapitre, nous supposons que le lecteur peut trouver les inverses et est capable de résoudre un système de congruences (Théorème des Restes Chinois) (voir : Nombres premiers et arithmétique modulaire).

Théorème de Wilson[modifier | modifier le wikicode]

Le théorème de Wilson est un simple résultat qui conduit à un nombre d'observations intéressantes dans la théorie élémentaire des nombres. Il établit le résultat suivant : Si p est un nombre premier, alors

Nous savons que l'inverse de p - 1 est p - 1, donc tout autre nombre peut être apparié avec son inverse et être éliminé. Par exemple, soit p = 7, nous considérons

1 × 2 × .. × 6 ≡ (2 × 4) × (3 × 5) × 1 × 6 = 6

Ce que nous avons fait, c'est apparier les nombres qui sont inverses les uns des autres, il nous reste alors les nombres qui sont inverse avec eux-même. Dans ce cas, ce sont les nombres 1 et 6.

Mais, il existe une difficulté technique. Pour un nombre premier général, p, comment savons-nous que 1 et p - 1 sont les seuls nombre mod p qui élevés au carrés donnent 1 ? Pour m non premier, il existe plus de 2 solutions à x2 ≡ 1 (mod m), par exemple, soit m = 15, alors x = 1, 14, 4, 11 sont les solutions de x2 ≡ 1 (mod m).

Néanmoins, nous pouvons montrer qu'il ne peut y avoir que (au plus) deux solutions à x2 ≡ 1 (mod p) lorsque p est premier. Nous le faisons par une simple démonstration par l'absurde. Vous pouvez passer la preuve suivante et admettre que le théorème de Wilson est vrai.

Soit p un nombre premier, et x2 ≡ 1 (mod p). Nous voulons prouver qu'il ne peut exister seulement que 2 solutions, c'est à dire x = 1, -1

il est évident, à partir de ci-dessus que x = 1, -1 (≡ p - 1) sont solutions. Supposons qu'il existe une autre solution, x = d, et d n'est pas égal à 1 ou -1. Puisque p est un nombre premier, nous savons que d - 1 doit avoir un inverse. Nous substituons x avec d et multiplions les deux cotés par l'inverse, c.a.d.

mais notre supposition initiale était que d ≠ -1. C'est une contradiction. Par conséquent, il ne peut exister que 2 solutions à x2 ≡ 1 (mod p).

Le petit théorème de Fermat[modifier | modifier le wikicode]

Il existe un remarquable petit théorème nommé en l'honneur de Fermat, le prince des mathématiciens amateurs. Il établit que si p est premier et pour a ≠ 0 donné alors

Ce théorème repose sur le fait que p est premier. Rappelons que si p est premier alors a ≠ 0 possède un inverse. Donc, pour tout b et c, nous devons avoir

si et seulement si

Une simple conséquence de ce qui précède est que les nombres suivants doivent tous être différents mod p

a, 2a , 3a, 4a, ..., (p-1)a

et il existe p - 1 de ces nombres ! Par conséquent, la liste précédente est simplement les nombres 1, 2, ... p - 1 dans un ordre différent. Prenons un exemple, si p = 5, et a = 2 :

1, 2, 3, 4

multiplions chacun des précédents par 2 mod 5, nous obtenons

2, 4, 1, 3

Ce sont les nombres originaux dans un ordre différent.

Ainsi, pour tout p et en utilisant le Théorème de Wilson (rappel : 1 × 2 × ... × (p-1) ≡ -1), nous obtenons

et d'un autre coté, nous obtenons aussi

En égalisant les deux résultats, nous obtenons

ce qui est essentiellement le petit théorème de Fermat.

L'arithmétique modulaire avec un m général[modifier | modifier le wikicode]

*Le Théorème des Restes Chinois revisité*[modifier | modifier le wikicode]

Cette section est plutôt théorique, et est destinée à justifier l'arithmétique que couvrira la section suivante. Par conséquent, il n'est pas nécessaire de comprendre entièrement ce qui est exposé ici, le lecteur peut choisir en toute quiétude de passer l'exposé ci-dessous.

Rappelons le Théorème des Restes Chinois (TRC) que nous avons exposé dans la section Arithmétique modulaire. Les congruences suivantes

ont une solution si et seulement si pgcd(n1,n2) divise (b - c).

Ce simple théorème décevant contient la clef de l'arithmétique modulo m (composé) ! Nous considèrerons le cas où m a seulement deux facteurs premiers, c'est à dire un nombre semi-premier, puis le cas général.

Supposons m = piqj, où p et q sont des nombres premiers distincts, alors chaque nombre naturel sous m (0, 1, 2, ..., m - 1) correspond uniquement à un système de congruences mod pi et mod qj. Ceci est dû au fait que pgcd(pi,qj) = 1, donc il divise tous les nombres.

Considérons un nombre n, il correspond à

pour deux nombres xn et yn. Si rn alors r correspond à

Maintenant, puisque r et n sont différents, nous devons avoir, soit xrxn et/ou yryn

Par exemple, prenons , alors nous pouvons construire la table suivante montrant les , pour chaque n (0, 1, 2 ... 11)

n n (mod 22) n (mod 3)
0 0 0
1 1 1
2 2 2
3 3 0
4 0 1
5 1 2
6 2 0
7 3 1
8 0 2
9 1 0
10 2 1
11 3 2

Note : comme prévu, chaque nombre correspond uniquement à deux systèmes de congruences mod 22 et mod 3.

Exercices

1. Considérons m = 45 = 32 × 5. Complètez la table ci-dessous et vérifiez que deux nombres quelconques doivent différer d'au moins une place dans la deuxième et la troisième colonne

n n (mod 32) n (mod 5)
0 0 0
1 1 1
2 2 2
...
44 ? ?

2. Supposons m = piqj, n correspond à

et r correspond à

Il est vrai que

et que

Arithmétique avec le TRC[modifier | modifier le wikicode]

L'exercice 2 ci-dessus a donné la plus grosse indication pour savoir comment le TRC peut nous aider avec l'arithmétique modulo m. Il n'est pas essentiel pour le lecteur de tout comprendre ci-dessus, à ce niveau. Nous décrirons comment le TRC peut nous aider avec l'arithmétique modulo m. Dans des termes simples, le TRC aide à casser un calcul modulo-m en de plus petits calculs modulo des facteurs premiers de m.

Comme toujours, considérons un exemple simple d'abord. Soit , nous voyons que m a deux nombres premiers distincts. Nous devons montrer la multiplication de 51 et 13 modulo 63 de deux manières. Premièrement, la manière standard

Alternativement, nous notons que

et

Nous pouvons représenter les deux expressions ci-dessus comme un couple (6,2). Nous faisons un petit abus de notation en écrivant 51 = (6,2). De manière similaire, nous écrivons 13 = (4,6). Lorsque nous multiplions avec les couples, nous multiplions les composants, i.e. (a,b) × (c,d) = (ac,bd),

Maintenant, résolvons

et

nous écrivons x = 6 + 9a, qui est la première congruence, puis

par conséquent, nous avons a = 3 + 7b, en substituant plus haut, nous obtenons

qui est la même réponse que nous avons obtenue à partir de la multiplication de 51 et 13 (mod 63) par la méthode standard !

Résumons ce que nous avons fait. En représentant les deux nombres (51 et 13) sous forme de deux couples et en multipliant les composants, nous finissons avec un autre couple. Et ce couple correspond au produit des deux nombres (mod m) via le Théorème des Restes Chinois.

Nous prendrons deux exemples supplémentaires. Soit , et multiplions 66 et 40 de deux manières. D'abord, la manière standard

et maintenant, la deuxième manière, 40 = (0,7) et 66 = (4,0) et

Pour le deuxième exemple, nous notons qu'il n'est pas nécessaire de s'arrêter à simplement deux facteurs premiers distincts. Prenons , et multiplions 900 et 647 (mod 975),

Pour l'autre manière, nous notons que 900 ≡ 0 (mod 3) ≡ 0 (mod 25) ≡ 3 (mod 13), et pour 647 ≡ 2 (mod 3) ≡ 22 (mod 25) ≡ 10 (mod 13),

maintenant, si nous résolvons les congruences suivantes

alors nous obtiendrons x ≡ 225 !

Pourquoi ? Casser l'arithmétique modulaire m en composants plus petits semble être un peu de travail. Prenons l'exemple des multiplications, d'abord, nous avons besoin d'exprimer chaque nombre comme un n-uplet (n est le nombre de facteurs premiers distincts de m), multiplier les composants, puis résoudre les n congruences résultantes. Assurément, ce travail est plus complexe que de multiplier simplement les deux nombres, puis de réduire le résultat modulo m. Alors, pourquoi se donner la peine d'étudier cela ?

En cassant un nombre m en facteurs premiers, nous avons un aperçu de la manière dont l'arithmétique fonctionne réellement. De manière plus importante, beaucoup de problèmes en arithmétique modulaire m peuvent être difficiles à résoudre, mais lorsque qu'ils sont cassés en composants, ils deviennent subitement plus faciles, par exemple le théorème de Wilson pour un m général (discuté ci-dessous).

Exercices[modifier | modifier le wikicode]

1. Montrer que l'addition peut aussi être effectuée par composants.

2. Multiplier par composants 32 et 84 (mod 134).

...

L'indicatrice d'Euler[modifier | modifier le wikicode]

Pour discuter de la forme la plus générale du théorème de Wilson et du petit théorème de Fermat mod m (non premier), il est intéressant de connaitre un résultat simple du mathématicien célèbre Euler. Plus précisément, nous voulons discuter d'une fonction, appelée la fonction indicatrice d'Euler, notée φ.

Les fonctions φ ne sont pas des choses très simples. Pour un nombre naturel quelconque m, φ(m) donne le nombre de n < m, tel que pgcd(n,m) = 1. En d'autres termes, elle calcule combien de nombre mod m ont un inverse. Nous discuterons de la valeur de φ(m) pour les cas simples d'abord, puis nous déduirons la formule pour un m général à partir des résultats basiques.

Par exemple, soit m = 5, alors φ(m) = 4. Comme 5 est un nombre premier, tous les nombres naturels différents de zéro inférieurs à 5 (1,2,3 and 4) sont premiers avec lui. Donc, il existe 4 nombres mod 5 qui ont des inverses. En fait, si m est premier, alors φ(m) = m - 1.

Nous pouvons généraliser ce qui précède à m = prp est premier. Dans ce cas, nous essayons d'employer un argument de comptage pour calculer φ(m). Notez qu'il existe pr nombres naturels inférieurs à m (0, 1, 2 ... pr - 1), et donc φ(m) = pr - (nombre de n < m tels que pgcd(n,m) ≠ 1). Nous avons effectué ceci parce qu'il est plus facile de compter le nombre de n sans inverse mod m.

Un élément, n mod m n'a pas d'inverse si et seulement si il partage un facteur commun avec m. Mais, tous les facteurs de m (non égaux à 1) sont un multiple de p. Donc, combien de multiples de p existent mod m ? Nous pouvons les lister, ce sont

où le dernier élément peut être écrit comme (pr-1 - 1)p, et donc, il existe multiples de p. Par conséquent, nous pouvons conclure

Nous avons maintenant toute la machinerie nécessaire pour déduire la formule de φ(m) pour un m quelconque.

Par le Théorème Fondamental de l'Arithmétique, tout nombre naturel m peut être exprimé de manière unique comme le produit de nombres premiers, c'est à dire

où pi pour i = 1, 2 ... r sont des nombres premiers distincts et ki sont des entiers positifs. Par exemple 1225275 = 3×52×17×312. A partir d'ici, le lecteur peut essayer de déduire le résultat suivant (le TRC peut aider).

La fonction indicatrice d'Euler φ

Supposons m exprimé de manière unique comme ci-dessous
  
alors
  

Le théorème de Wilson[modifier | modifier le wikicode]

Le théorème de Wilson pour un m général établit que le produit de tous les éléments inversibles mod m

égal -1 si m a seulement un facteur premier, ou m = 2pk pour un certain nombre premier p
égal à 1 pour tous les autres cas

Un élément inversible mod m est un nombre naturel n < m tel que pgcd(n, m) = 1. Un élément auto-inversible est un élément dont l'inverse est lui-même.

Dans la démonstration du théorème de Wilson pour un nombre premier p, les nombres de the numbers 1 à p - 1 ont tous des inverses. Ceci n'est pas vrai pour un m général. En fait, il est certain que (m - 1)! ≡ 0 (mod m), pour cette raison, nous considérons à la place le produit de tous les éléments inversibles mod m.

Pour le cas où m = p est un nombre premier, nous avons aussi fait appel au fait que 1 et p - 1 sont les seuls éléments qui, élevés au carré, donnent 1. En fait, pour m = pk, 1 et m - 1 (≡ -1) sont les seuls éléments auto-inversibles (voir les exercices). Mais, pour un m général, ceci n'est pas vrai. Prenon par exemple m = 21. En arithmétique modulo 21 chacun des nombres suivants est lui-même un inverse

1, 20, 8, 13

donc, comment pouvons-nous dire que le produit de tous les éléments inversibles est égal à 1 ?

Nous utilisons le TRC décrit précédement. Considérons le cas où m = 2pk. Par le TRC, chaque élément mod m peut être représenté comme un couple (a,b) où a peut prendre la valeur 0 ou 1 tandis que b peut prendre la valeur 0, 1, ..., ou pk - 1. Chaque couple correspond uniquement à une paire de congruences et la multiplication peut être exécutée par composants.

En utilisant l'information précédente, nous pouvons facilement lister tous les éléments auto-inversibles, parce que (a,b)2 ≡ 1 signifie (a2,b2) = (1,1), donc a est un élément inversible mod 2 et b est un élément inversible mod pk, donc a ≡ 1 ou -1, b ≡ 1 ou -1. Mais mod 2 1 ≡ -1, donc a = 1. Par conséquent, il existe deux éléments qui sont auto-inversibles mod m = 2pk, ce sont (1,1) = 1, et (1, -1) = m - 1 . Donc, dans ce cas, le résultat est le même, comme m possède seulement un facteur premier unique.

Pour le cas où m possède plus d'un facteur premier et m≠ 2pk. Disons m a n facteurs premiers alors m peut être représenté comme un n-uplet. Disons que m possède 3 facteurs premiers distincts, alors tous les éléments auto-inversibles de m sont

  1. (1,1,1)
  2. (1,1,-1)
  3. (1,-1,1)
  4. (1,-1,-1)
  5. (-1,1,1)
  6. (-1,1,-1)
  7. (-1,-1,1)
  8. (-1,-1,-1)

leur produit est (1,1,1) qui correspond à 1 mod m.

Exercice[modifier | modifier le wikicode]

1. Soit p un nombre premier. Montrer que dans l'arithmétique modulo pk, 1 et pk - 1 sont les seuls éléments auto-inversibles.

...plus à venir

...

Le petit théorème de Fermat[modifier | modifier le wikicode]

Comme indiqué dans la section précédente, tous les éléments ne sont pas inversibles (c.a.d. possède un inverse) mod m. Une version généralisée du dernier théorème de Fermat utilise la fonction indicatrice d'Euler, il énonce

pour tous les a ≠ 0 satisfaisant pgcd(a,m) = 1. Ceci est facile à voir à partir de la version généralisée du théorème de Wilson. Nous utilisons une technique similaire à partir de la démonstration du petit théorème de Fermat. Nous avons

où les bi's sont tous les éléments inversibles mod m. Par le théorème de Wilson, le produit de tous les éléments inversibles égaux à d (= 1 ou -1). Donc, nous obtenons

qui est essentiellement l'énoncé du petit théorème de Fermat.

Bien que le petit théorème de Fermat est très net, il est imprécis dans un certain sens. Par exemple, prenons m = 15 = 3 × 5, nous savons que si a possède un inverse mod 15 alors aφ(15) = a8 ≡ 1 (mod 15). Mais 8 est trop grand, tout ce que nous avons besoin est 4, a4 ≡ 1 (mod 15) pour tous les a avec un inverse (le lecteur peut vérifier).

La fonction de Carmichael λ(m) est le plus petit nombre tel que aλ(m) ≡ 1 (mod m) pour un a inversible. Une question dans Ensemble de problèmes traite de cette fonction.

Exercices[modifier | modifier le wikicode]

...plus à venir

La factorisation double-torsion[modifier | modifier le wikicode]

Il est clair que factoriser un grand nombre peut être extrêmement difficile. Par exemple, étant donné 76 372 591 715 434 667, qui est le produit de deux nombres premiers, le lecteur peut-il le factoriser ? Sans l'aide d'un bon logiciel d'algèbre, la tâche risque d'être impossible. A ce jour, il n'existe pas d'algorithme connu efficient pour factoriser un nombre en facteurs premiers.

Néanmoins, sous certaines circonstances spéciales, factoriser peut être facile. Nous considèrerons la méthode de factorisation double-torsion. Un élément double-torsion dans l'arithmétique modulaire m est un nombre a tel que a2 ≡ 1 (mod m).

Considérons un exemple en arithmétique modulo 21. Notez qu'en utilisant le TRC, nous pouvons représenter tout nombre mod 21 comme un couple. Les éléments double-torsion sont 1 = (1,1), 13 = (1,-1), 8 = (-1,1) et 20 = (-1,-1). Les nombres 13 et 8 sont intéressants, parceque 1 et 20 (≡ - 1) sont évidemment double-torsion, nous appelons ces nombres double-torsion triviaux.

Maintenant, 13 + 1 = (1,-1) + (1,1) = (2,0). Par conséquent 13 + 1 = 14 est un élément partageant un facteur commun avec 21, comme le deuxième composant dans la représentation en couple de 14 est zéro. Par conséquent PGCD(14,21) = 7 est un facteur de 21.

L'exemple ci-dessus est très stupide parceque tout le monde peut factoriser 21. Mais qu'en est-il de 24 131 ? Factoriser n'est pas si facile. Mais, étant donné que 12 271 est un élément double-torsion non-trivial (c.a.d. ≠ 1 ou -1), alors nous pouvons conclure que pgcd(12271 + 1,24131) et pgcd(12271 - 1,24131) sont des facteurs de 24 131. En effet, pgcd(12272,24131) = 59 et pgcd(12270,24131) = 409 sont tous les deux des facteurs de 24 131.

Plus généralement, soit m un nombre composé, et t un élément double-torsion non-trivial mod m c.a.d. t ≠ 1, -1. Alors

pgcd(t + 1,m) divise m, et
pgdc(t - 1,m) divise m

ceci peut être expliqué en utilisant le TRC.

Nous expliquerons le cas où m = pq, p et q sont des nombres premiers. Etant donné t est un élément double-torsion non-trivial, alors t a pour représentation (1,-1) ou (-1,1). Supposons t = (-1,1) alors t + 1 = (-1,1) + (1,1) = (0,2), par conséquent t + 1 doit avoir un multiple de p par conséquent pgcd(t,m) = p. L'autre cas t - 1 = (-1,1) - (1,1) = (-2,0) et donc pgcd(t - 1,m) = q.

Donc, si nous avons un élément double-torsion non-trivial alors nous avons effectivement trouvé un (et sans doute plus) facteur premier, qui donne la factorisation du nombre. Dans les applications cryptographiques publiques les plus modernes, pour casser le système nous avons besoin seulement de factoriser un nombre avec deux facteurs premiers. De ce point de vue, la méthode de factorisation double-torsion est effroyablement efficiente.

Bien sur, trouver un élément double-torsion non-trivial n'est pas une tâche facile non plus. Donc, la banque par internet est encore sûre pour le moment. De cette manière, 76372591715434667 = 224364191 × 340395637.

Exercices[modifier | modifier le wikicode]

1. Etant donné que 18815 est un élément double-torsion mod 26176. Factoriser 26176.

...plus à venir'