Sauter au contenu
Logo image

Algèbre abstraite Théorie et applications

Thomas W. Judson

Section 16.5 Une application à la conception de logiciels

Le théorème chinois des restes est un résultat de théorie élémentaire des nombres portant sur la résolution de systèmes de congruences simultanées. Le mathématicien chinois Sun-tsï écrivit sur ce théorème au premier siècle après J.-C. Ce théorème a des conséquences intéressantes dans la conception de logiciels pour les processeurs parallèles.
🔗

Démonstration.

L’équation \(x \equiv a \pmod{m}\) admet une solution car \(a + km\) satisfait l’équation pour tout \(k \in {\mathbb Z}\text{.}\) Il faut montrer qu’il existe un entier \(k_1\) tel que
\begin{equation*} a + k_1 m \equiv b \pmod{n}\text{.} \end{equation*}
Cela revient à montrer que
\begin{equation*} k_1 m \equiv (b-a) \pmod{n} \end{equation*}
admet une solution pour \(k_1\text{.}\) Puisque \(m\) et \(n\) sont premiers entre eux, il existe des entiers \(s\) et \(t\) tels que \(ms + nt = 1\text{.}\) Par conséquent,
\begin{equation*} (b-a) ms = (b-a) -(b-a) nt\text{,} \end{equation*}
soit
\begin{equation*} [(b-a)s]m \equiv (b-a) \pmod{n}\text{.} \end{equation*}
Posons maintenant \(k_1 = (b-a)s\text{.}\)
🔗
Pour montrer que deux solutions quelconques sont congruentes modulo \(mn\text{,}\) soient \(c_1\) et \(c_2\) deux solutions du système. C’est-à-dire,
\begin{align*} c_i & \equiv a \pmod{m}\\ c_i & \equiv b \pmod{n} \end{align*}
pour \(i = 1, 2\text{.}\) Alors
\begin{align*} c_2 & \equiv c_1 \pmod{m}\\ c_2 & \equiv c_1 \pmod{n}\text{.} \end{align*}
Donc \(m\) et \(n\) divisent tous deux \(c_1 - c_2\text{.}\) Par conséquent, \(c_2 \equiv c_1 \pmod{mn}\text{.}\)
🔗
🔗

Exemple 16.5.2.

Résolvons le système
\begin{align*} x & \equiv 3 \pmod{4}\\ x & \equiv 4 \pmod{5}\text{.} \end{align*}
À l’aide de l’algorithme d’Euclide, on peut trouver des entiers \(s\) et \(t\) tels que \(4s + 5t = 1\text{.}\) Deux tels entiers sont \(s = 4\) et \(t = -3\text{.}\) Par conséquent,
\begin{equation*} x = a + k_1 m = 3 + 4k_1 = 3 + 4[(5 - 4)4] = 19\text{.} \end{equation*}
🔗
🔗

Démonstration.

Nous utiliserons le raisonnement par récurrence sur le nombre d’équations du système. S’il y a \(k= 2\) équations, alors le théorème est vrai d’après le Lemme 16.5.1. Supposons maintenant que le résultat est vrai pour un système d’au plus \(k\) équations et cherchons une solution de
\begin{align*} x & \equiv a_1 \pmod{n_1}\\ x & \equiv a_2 \pmod{n_2}\\ & \vdots\\ x & \equiv a_{k+1} \pmod{n_{k+1}}\text{.} \end{align*}
En considérant les \(k\) premières équations, il existe une solution unique modulo \(n_1 \cdots n_k\text{,}\) disons \(a\text{.}\) Puisque \(n_1 \cdots n_k\) et \(n_{k+1}\) sont premiers entre eux, le système
\begin{align*} x & \equiv a \pmod{n_1 \cdots n_k }\\ x & \equiv a_{k+1} \pmod{n_{k+1}} \end{align*}
admet une solution unique modulo \(n_1 \ldots n_{k+1}\) d’après le lemme.
🔗
🔗

Exemple 16.5.4.

Résolvons le système
\begin{align*} x & \equiv 3 \pmod{4}\\ x & \equiv 4 \pmod{5}\\ x & \equiv 1 \pmod{9}\\ x & \equiv 5 \pmod{7}\text{.} \end{align*}
D’après le Exemple 16.5.2, nous savons que \(19\) est une solution des deux premières congruences et que toute autre solution du système est congrue à \(19 \pmod{20}\text{.}\) Nous pouvons donc réduire le système à un système de trois congruences :
\begin{align*} x & \equiv 19 \pmod{20}\\ x & \equiv 1 \pmod{9}\\ x & \equiv 5 \pmod{7}\text{.} \end{align*}
En résolvant les deux équations suivantes, on peut réduire le système à
\begin{align*} x & \equiv 19 \pmod{180}\\ x & \equiv 5 \pmod{7}\text{.} \end{align*}
En résolvant ce dernier système, on trouve que \(19\) est une solution du système, unique modulo \(1260\text{.}\)
🔗
🔗
Une application intéressante du théorème chinois des restes dans la conception de logiciels informatiques est que ce théorème permet de décomposer un calcul portant sur de grands entiers en plusieurs calculs moins redoutables. Un ordinateur ne peut effectuer des calculs sur des entiers que jusqu’à une certaine taille en raison de la taille de son processeur, qui est généralement un processeur 32 ou 64 bits. Par exemple, le plus grand entier disponible sur un ordinateur équipé d’un processeur 64 bits est
\begin{equation*} 2^{63} - 1 = 9{,}223{,}372{,}036{,}854{,}775{,}807\text{.} \end{equation*}
Des processeurs plus grands, de 128 ou 256 bits, ont été proposés ou sont en cours de développement. On parle même d’un processeur 512 bits. Le plus grand entier qu’une telle puce pourrait stocker serait \(2^{511} - 1\text{,}\) soit un nombre de 154 chiffres. Cependant, il faudrait travailler avec des nombres bien plus grands pour décrypter des schémas de chiffrement sophistiqués.
🔗
Des logiciels spéciaux sont nécessaires pour les calculs portant sur de grands entiers qui ne peuvent pas être additionnés directement par la machine. En utilisant le théorème chinois des restes, on peut décomposer les additions et les multiplications de grands entiers en calculs que l’ordinateur peut effectuer directement. Cela est particulièrement utile sur les ordinateurs à traitement parallèle, qui ont la capacité d’exécuter plusieurs programmes simultanément.
🔗
La plupart des ordinateurs ont une seule unité centrale de traitement (CPU) contenant un processeur et ne peuvent additionner que deux nombres à la fois. Pour additionner une liste de dix nombres, le CPU doit effectuer neuf additions en séquence. En revanche, un ordinateur à traitement parallèle possède plusieurs CPU. Un ordinateur équipé de 10 CPU, par exemple, peut effectuer 10 additions différentes simultanément. Si l’on peut décomposer un grand entier en parties et envoyer chaque partie à un CPU différent, puis en effectuant simultanément plusieurs additions ou multiplications sur ces parties, on peut travailler avec un entier que l’ordinateur ne pourrait pas traiter dans sa totalité.
🔗

Exemple 16.5.5.

Supposons que nous souhaitons multiplier \(2134\) par \(1531\text{.}\) Nous utiliserons les entiers \(95\text{,}\) \(97\text{,}\) \(98\) et \(99\) car ils sont premiers entre eux. On peut décomposer chaque entier en quatre parties :
\begin{align*} 2134 & \equiv 44 \pmod{95}\\ 2134 & \equiv 0 \pmod{97}\\ 2134 & \equiv 76 \pmod{98}\\ 2134 & \equiv 55 \pmod{99} \end{align*}
et
\begin{align*} 1531 & \equiv 11 \pmod{95}\\ 1531 & \equiv 76 \pmod{97}\\ 1531 & \equiv 61 \pmod{98}\\ 1531 & \equiv 46 \pmod{99}\text{.} \end{align*}
En multipliant les équations correspondantes, on obtient
\begin{align*} 2134 \cdot 1531 & \equiv 44 \cdot 11 \equiv 9 \pmod{95}\\ 2134 \cdot 1531 & \equiv 0 \cdot 76 \equiv 0 \pmod{97}\\ 2134 \cdot 1531 & \equiv 76 \cdot 61 \equiv 30 \pmod{98}\\ 2134 \cdot 1531 & \equiv 55 \cdot 46 \equiv 55 \pmod{99}\text{.} \end{align*}
Chacun de ces quatre calculs peut être envoyé à un processeur différent si notre ordinateur dispose de plusieurs CPU. D’après le calcul ci-dessus, nous savons que \(2134 \cdot 1531\) est une solution du système
\begin{align*} x & \equiv 9 \pmod{95}\\ x & \equiv 0 \pmod{97}\\ x & \equiv 30 \pmod{98}\\ x & \equiv 55 \pmod{99}\text{.} \end{align*}
Le théorème chinois des restes nous dit que les solutions sont uniques modulo \(95 \cdot 97 \cdot 98 \cdot 99 = 89{,}403{,}930\text{.}\) En résolvant ce système de congruences pour \(x\text{,}\) on trouve que \(2134 \cdot 1531 = 3{,}267{,}154\text{.}\)
🔗
La conversion du calcul en quatre sous-calculs prendra un certain temps de calcul. De plus, la résolution du système de congruences peut également prendre un temps considérable. Cependant, si l’on doit effectuer de nombreux calculs sur un ensemble particulier de nombres, il est judicieux de transformer le problème comme nous l’avons fait ci-dessus et d’effectuer les calculs nécessaires simultanément.
🔗
🔗
🔗
PrécédentTopSuivant