TD 2
Exercice 14 - Questions de cours
Rappels.
Un anneau \((A, +, \times)\) est un ensemble \(A\) muni de deux lois de composition interne \(+\) et \(\times\) telles que :
- \((A, +)\) est un groupe commutatif,
- \((A, \times)\) est un monoïde,
- \(\forall a, b, c \in A, a \times (b + c) = a \times b + a \times c, (a + b) \times c = a \times c + b \times c\) (distributivité).
Un anneau \((A, +, \times)\) est dit commutatif si \(\forall a, b \in A, a \times b = b \times a\), en d'autres termes, si \((A, \times)\) est un monoïde commutatif.
Dans un anneau \((A, +, \times)\),
- un élément \(a \in A\) est inversible s'il existe \(b \in A\) tel que \(a \times b = b \times a = 1\),
- un élément \(a \in A^\times\) est un diviseur de zéro s'il existe \(b \in A^\times\) tel que \(a \times b = 0\) ou \(b \times a = 0\).
- un élément \(a \in A\) est irréductible s'il n'est pas inversible et qu'il ne peut pas être écrit comme produit de deux éléments non inversibles.
Un anneau \((A, +, \times)\) est dit intègre s'il est commutatif et sans diviseurs de zéro.
Q1.
Un diviseur de zéro ne peut pas être inversible. En effet, soit \(a \in A\) un diviseur de zéro, au sens où il existe \(b \in A, b \neq 0\) tel que \(a \times b = 0\). Supposons que \(a\) soit inversible, c'est-à-dire qu'il existe \(c \in A\) tel que \(a \times c = c \times a = 1\). Alors \(c \times a \times b = 1 \times b = b\). Or, on a aussi \(c \times a \times b = c \times 0 = 0\), donc \(b = 0\), ce qui est absurde.
Pour la dernière question, \(\mathbb{Z}/2\mathbb{Z}\) est intègre, alors que \(\mathbb{Z}/6\mathbb{Z}\) ne l'est pas : \(2 \mod 6 \times_{\mod 6} 3 \mod 6 = 0 \mod 6\).
Q3.
\(\mathbb{Z}\) est intègre, car c'est un anneau commutatif sans diviseurs de zéro. Les éléments irréductibles de \(\mathbb{Z}\) sont les nombres premiers et leurs opposés.
Exercice 15 - Sur le PGCD et son calcul
Q1, Q2.
On observe dans le TD que \(1170 = 117 \times 10 = 2 \times 5 \times 117\), puis \(117 = 13 \times 9\), car \(1+1+7=9\) implique que \(117\) est divisible par \(9\). De même, \(330 = 33 \times 10 = (3 \times 11) \times (2 \times 5)\). On arrive finalement à
\begin{align*} a = 1170 &= 2 \times 3^2 \times 5 \qquad \times 13, \\ b = 330 &= 2 \times 3 \times 5 \times 11. \end{align*}On voit déjà qu'à partir de la factorisation de \(1170\) et \(330\), \(\gcd(1170, 330) = 2 \times 3 \times 5 = 30\). Mais, oublions cette observation pour l'instant, et continuons avec Q1 et Q2.
Si \(c\) est un facteur de \(1170\), alors \(c\) est de la forme \(2^{p_1} \times 3^{p_2} \times 5^{p_3} \times 13^{p_4}\), où \(p_1 \in \{0, 1\}\), \(p_2 \in \{0, 1, 2\}\), \(p_3 \in \{0, 1\}\), et \(p_4 \in \{0, 1\}\). On en déduit que \(1170\) a \(2 \times 3 \times 2 \times 2 = 24\) diviseurs. De même, \(330\) a \(2 \times 2 \times 2 \times 2 = 16\) diviseurs. Si on veut vraiment énumérer \(D(a)\) et \(D(b)\), on arrive à
\begin{align*} D(a) &= \{1, 2, 3, 5, 6, 9, 10, 13, 15, 18, 26, 30, 39, 45, 65, 78, 90, 117, 130, 195, 234, 390, 585, 1170\}, \\ D(b) &= \{1, 2, 3, 5, 6, 10, 11, 15, 22, 30, 33, 55, 66, 110, 165, 330\}, \end{align*}et donc \(D(a) \cap D(b) = \{1, 2, 3, 5, 6, 10, 15, 30\}\), d'où \(\gcd(1170, 330) = \max(D(a) \cap D(b)) = 30\).
(Pendant le TD, j'utilise \(\textrm{pgcd}\) pour désigner le PGCD ; ici, j'utilise \(\gcd\) puisque c'est la notation standard.)
Q3, Q4.
\(1537\) et \(1643\) sont difficiles à factoriser.
Mais, si on traite Q5 avant Q4, en appliquant l'algorithme d'Euclide, on a
\begin{align*} \gcd(1643, 1537) &= \gcd(1643 \% 1537, 1537) = \gcd(106, 1537) \\ &= \gcd(106, 1537 \% 106) = \gcd(106, 53) \\ &= 53. \end{align*}Donc 53 est le PGCD de 1643 et 1537. On en déduit facilement que \(1643 = 31 \times 53\) et \(1537 = 29 \times 53\).
Q5.
La relation de Bachet-Bézout dit que si \(a\) et \(b\) sont des entiers (ou plus généralement des éléments d'un anneau euclidien, i.e., un anneau où on peut définir un algorithme d'Euclide), alors il existe \(u, v \in \mathbb{Z}\) tels que \(\gcd(a, b) = au + bv\). Dans le cas où \(a = 1643\) et \(b = 1537\), on a donc l'existence de \(u, v \in \mathbb{Z}\) tels que \(53 = 1643u + 1537v\).
Q6.
Le PPCM de \(a\) et \(b\) est défini comme le plus petit commun multiple de \(a\) et \(b\), et il se déduit à partir de la relation \(a \times b = \gcd(a, b) \times \textrm{lcm}(a, b)\).
Exercice 16 - Lagrange, Bézout et les groupes
Q1.
L'ordre d'un élément \(g\) d'un groupe fini est le plus petit entier strictement positif \(k\) tel que \([k]g = [0]g\).
Dans le reste de l'exercice, on note \(\omega(a)\) l'ordre de l'élément \(a\) dans le groupe \((G, \circ)\), dont l'élément neutre est \(0\).
Q2.
Soit \(k \mod 30\) un élément du groupe \((\mathbb{Z}/30\mathbb{Z},+)\). Si on regarde la formule dans Q4, on a
\begin{equation*} \omega(k \mod 30) = \omega([k](1 \mod 30)) = \frac{\omega(1 \mod 30)}{\gcd(\omega(1 \mod 30), k)} = \frac{30}{\gcd(30, k)}. \end{equation*}Vérifions que
- Pour \(k\in\lbrace 1, 7, 11, 13, 17, 19, 23, 29\rbrace\), on a \(\omega(k \mod 30) = 30\).
- Pour \(k\in\lbrace 2, 4, 8, 14, 16, 22, 26, 28\rbrace\), on a \(\omega(k \mod 30) = 15\).
- Pour \(k\in\lbrace 3, 9, 21, 27\rbrace\), on a \(\omega(k \mod 30) = 10\).
- Pour \(k\in\lbrace 5, 25\rbrace\), on a \(\omega(k \mod 30) = 6\).
- Pour \(k\in\lbrace 6, 12, 18, 24\rbrace\), on a \(\omega(k \mod 30) = 5\).
- Pour \(k\in\lbrace 10, 20\rbrace\), on a \(\omega(k \mod 30) = 3\).
- Pour \(k\in\lbrace 15\rbrace\), on a \(\omega(k \mod 30) = 2\).
- Pour \(k\in\lbrace 0\rbrace\), on a \(\omega(k \mod 30) = 1\).
Q3.
On veut montrer que si \([k]a=0\), alors \(\omega(a)\) divise \(k\), i.e. le reste de la division euclidienne de \(k\) par \(\omega(a)\) est \(0\). Supposons que la division euclidienne de \(k\) par \(\omega(a)\) donne \(k = q\omega(a) + r\) avec \(0 \leq r < \omega(a)\). On a alors
\begin{equation*} [k]a = [q\omega(a) + r]a = [q\omega(a)]a \circ [r]a = 0 \circ [r]a = [r]a. \end{equation*}Mais \([k]a = 0\), donc \([r]a = 0\), et donc \(r = 0\) par la minimalité de \(\omega(a)\).
Q4.
Rappelons que d'après Q3, \([m]n=0 \implies \omega(n)\mid m\).
Pour montrer que \(\omega([k]a) = \frac{\omega(a)}{\gcd(\omega(a),k)}\), il suffit de montrer que \(\omega([k]a) \mid \frac{\omega(a)}{\gcd(\omega(a),k)}\) et que \(\frac{\omega(a)}{\gcd(\omega(a),k)} \mid \omega([k]a)\).
Pour montrer la première relation, on utilise Q3 : il suffit de montrer que \([\frac{\omega(a)}{\gcd(\omega(a),k)}][k]a=0\). Or, on a
\begin{equation*} [\frac{\omega(a)}{\gcd(\omega(a),k)}][k]a = [\frac{k}{\gcd(\omega(a),k)}][\omega(a)]a = [0]a. \end{equation*}Pour montrer la deuxième relation, on réutilise Q3, en cherchant un \(n\) tel que \([\omega([k]a)]n=0\). Un choix naturel est donc \(n=[k]a\), et on a
\begin{equation*} 0 = [\omega([k]a)][k]a = [\omega([k]a)k]a, \end{equation*}ce qui implique que \(\omega(a) \mid \omega([k]a)k\), et donc \(\frac{\omega(a)}{\gcd(\omega(a),k)} \mid \omega([k]a)\frac{k}{\gcd(\omega(a),k)}\).
Or, \(\frac{\omega(a)}{\gcd(\omega(a),k)}\) et \(\frac{k}{\gcd(\omega(a),k)}\) sont premiers entre eux, donc \(\frac{\omega(a)}{\gcd(\omega(a),k)} \mid \omega([k]a)\) par le lemme de Gauss.
Q5.
Pour montrer que \(\omega(a \circ b) \mid \textrm{lcm}(\omega(a), \omega(b))\), il suffit de montrer que \([\textrm{lcm}(\omega(a), \omega(b))](a \circ b) = 0\). Effectivement, dans un groupe commutatif, on a
\begin{equation*} [\textrm{lcm}(\omega(a), \omega(b))](a \circ b) = [\textrm{lcm}(\omega(a), \omega(b))]a \circ [\textrm{lcm}(\omega(a), \omega(b))]b = 0 \circ 0 = 0, \end{equation*}\(\textrm{lcm}(\omega(a), \omega(b))\) étant un multiple commun de \(\omega(a)\) et \(\omega(b)\).
Dans le cas où \(\omega(a)\) et \(\omega(b)\) sont premiers entre eux, on a en fait \(\omega(a \circ b) = \textrm{lcm}(\omega(a), \omega(b))\). Montrons donc que \(\textrm{lcm}(\omega(a), \omega(b)) \mid \omega(a \circ b)\).
Pour le choix de \(n\) tel que \([\omega(a \circ b)]n=0\), on a naturellement \(n=a \circ b\), ce qui donne \(0 = [\omega(a \circ b)](a \circ b) = [\omega(a \circ b)]a \circ [\omega(a \circ b)]b\). Pour annuler le premier terme, il suffit de passer \([\omega(a)]\) dans les deux côtés, ce qui donne
\begin{equation*} 0 = [\omega(a)]0 = [\omega(a)][\omega(a \circ b)]a \circ [\omega(a)][\omega(a \circ b)]b = [\omega(a)\omega(a \circ b)]b. \end{equation*}Ainsi, \(\omega(b) \mid \omega(a)\omega(a \circ b)\), et donc \(\omega(b) \mid \omega(a \circ b)\) par le lemme de Gauss.
De même, si on annule le deuxième terme en passant \([\omega(b)]\) dans les deux côtés, on aura \(\omega(a) \mid \omega(a \circ b)\) à la fin. Donc \(\textrm{lcm}(\omega(a), \omega(b)) \mid \omega(a \circ b)\).
Exercice 5 - Poly-alphabétique
Q1.
Pour la clé \(C=(c_0, c_1, \ldots, c_{l-1})\), on découpe le texte en blocs de longueur \(l\), et on chiffre la $i$-ème lettre de chaque bloc avec \(c_i\).
i mod l
-------------
t_{0} ... | t_{i} | ... t_{l-1}
t_{l} ... | t_{l+i} | ... t_{2l-1}
... | | ...
t_{kl} ... | t_{kl+i} | ... t_{(k+1)l-1}
-------------
chiffré avec c_{i}
Q2.
On écrit la table suivante pour retrouver facilement l'ordre des lettres :
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
|---|---|---|---|---|---|---|---|---|---|---|
| 0 | A | B | C | D | E | F | G | H | I | J |
| 1 | K | L | M | N | O | P | Q | R | S | T |
| 2 | U | V | W | X | Y | Z |
Avec la clé CIPHER, le chiffrement de message n'est rien d'autre que la somme des lettres du message et de la clé répétée (modulo 26). Par exemple, C+L=2+11=13=N, I+A=8+0=8=I, etc.
LATTAQ UEESTP REVUEP OURDEM AIN + CIPHER CIPHER CIPHER CIPHER CIP --------------------------------- NIIEAH WMTZXG TMKBIG QCGKID CQC
Avec la clé CESAR, le déchiffrement de message devient donc la soustraction des lettres du message et de la clé répétée (modulo 26).
XSMSR XIRDV LEIUV NUMEJ RSANK U - CESAR CESAR CESAR CESAR CESAR C --------------------------------- VOUSA VEZDE JAQUE LQUES POINT S
Q3.
La réponse officielle est la substitution poly-alphabétique.
(Si la réponse n'est pas satisfaisante, on peut aussi dire que le chiffrement de Vigenère est un isomorphisme entre deux monoïdes libres engendrés par la puissance de même ordre de deux alphabets finis …)
Exercice 6 - Indice de Coïncidence
Q1.
L'indice de coïncidence est la probabilité d'avoir des lettres identiques en choisissant deux lettres au hasard dans un texte. Il est défini comme
\begin{equation*} IC = \sum_{i\in\mathcal{A}} \frac{n_i(n_i - 1)}{n(n-1)}, \end{equation*}où \(\mathcal{A}\) est l'alphabet, \(n_i\) est le nombre d'occurrences de la lettre \(i\) dans le texte, et \(n\) est le nombre total de lettres dans le texte.
Q2.
La définition de l'indice de coïncidence dépend de la longueur du texte. Supposons donc qu'on a 10006 lettres dans le texte. D'après la formule, et un peu de calcul (bien sûr, en Python), on trouve \(IC = 1266183/16685005 \simeq 0.075\).
Q3.
Notons \(\sigma:\mathcal{A}\to\mathcal{A}\) la substitution (qui est par définition une bijection). On a alors
\begin{equation*} IC_{\sigma} = \sum_{i\in\mathcal{A}} \frac{n_{\sigma(i)}(n_{\sigma(i)} - 1)}{n(n-1)} = \sum_{\sigma^{-1}(i)\in\mathcal{A}} \frac{n_i(n_i - 1)}{n(n-1)} = \sum_{i\in\mathcal{A}} \frac{n_i(n_i - 1)}{n(n-1)} = IC. \end{equation*}Donc, l'indice de coïncidence est invariant par substitution ; un texte chiffré a donc le même indice de coïncidence que le texte en clair.
On connaît que pour les textes en français, l'indice de coïncidence est autour de 0.074, alors que cela prend une valeur plus petite pour les textes en anglais. Il est donc un distingueur de langues.
Exercice 7 - Test de Kasiski vs Indice de Coïncidence
Q1.
Il s'agit de questions du cours.
Q2.
On observe que
| Répétition | Distance |
|---|---|
| BEAV | \(25-20=5\) |
| JOO | \(345-234=111=3\times 37\) |
| SSTBPK | \(456-36=420=2^2\times 3\times 5\times 7\) |
| YEA | \(102-7=28=2^2\times 7\), \(497-102=395=5\times 79\) |
La répétition la plus convaincante est donc SSTBPK, avec une distance de 420. Il est donc probable que la longueur de la clé est un facteur de 420.
Q3, Q4.
Supposons que la longueur de la clé est \(k\). Pour chaque \(i\in [0, k-1]\), les caractères à la position \(i mod k\) sont chiffrés avec la même lettre de la clé. D'après Q3 dans l'exercice 6, le IC sur la sous-chaîne composée de ces caractères devrait être proche de celui d'une langue plutôt que d'un texte aléatoire, et le même résultat devrait être vrai pour le IC moyen.
Si on regarde dans le tableau, on voit que pour \(k=7\) et \(k=14\), le IC moyen est proche de 0,067, qui est la valeur attendue pour un texte en anglais. On en déduit donc que la longueur de la clé est 7.
Q5.
Il s'agit d'un devoir maison.
POELIKEHAW THORNECAME INWITHTHED ECLINEOFTH EROMANTICS CHOOLANDNO NEDELIGHTE DMORETHANH ETOLAUGHAT ITSCALAMIT YYETHISHEA RTWASWITHT HEROMANCER SANDTHEIRO RIENTALORG OTHICEFFEC TSHISINVEN TIONSORICH INTHEPROSE TALESSEEME DTODESERTH IMWHENHEWR OTEVERSEAN DHISJUDGME NTTOLDHIMT HATLONGROM ANTICPOEMS DEPENDMORE UPONINCIDE NTTHANINSP IRATIONAND THATTOUTTE RTHEPOETRY OFROMANCEL YRICSWOULD SUFFICEHEN CEHISTHEOR YCLEARLYFI TTEDTOHISO WNLIMITATI ONSTHATALO NGPOEMISAF LATCONTRAD ICTIONINTE RMSTHECOMP ONENTSOFTH ERAVENAREF EWANDSIMPL EAMANABIRD ANDTHEPHAN TASMALMEMO RYATAWOMAN