Finish writing solution to test.

1 files changed, 158 insertions, 3 deletions

diff --git a/controle-20121127.tex b/controle-20121127.tex
index 1d3c8d5..eae9647 100644
--- a/controle-20121127.tex
+++ b/controle-20121127.tex
@@ -225,6 +225,13 @@ que ce polynôme est irréductible.  On pose $E = \mathbb{F}_2[t]/(f)$.
 
 (1) Combien d'éléments $E$ a-t-il ?  Combien d'éléments $E^\times$ (le
 groupe des inversibles de $E$) a-t-il ?
+\begin{corrige}
+Comme $f$ est de degré $8$, l'anneau $E$ a $2^8 = 256$ éléments
+(représentés de façon unique par tous les polynômes de degré $<8$ sur
+$\mathbb{F}_2$).  Comme $f$ est irréductible, cet anneau est, en fait,
+un corps.  Ses éléments inversibles sont donc les éléments non nuls
+de $E$, et $E^\times$ a $255$ éléments.
+\end{corrige}
 
 On désignera par $\alpha \in E$ (plutôt que $\bar t$) la classe de $t$
 modulo $f$.
@@ -232,9 +239,45 @@ modulo $f$.
 (2) Que peut-on dire \textit{a priori} de l'ordre multiplicatif
 de $\alpha$ ?  C'est-à-dire : quelles sont les valeurs \textit{a
   priori} possibles ?  (Remarque : $255 = 3 \times 5 \times 17$.)
+\begin{corrige}
+D'après le théorème de Lagrange, l'ordre multiplicatif de $\alpha$
+doit diviser l'ordre du groupe $E^\times$, soit $255$.  C'est donc un
+des nombres $3, 5, 17,\penalty0\, 3\times 5{=}15, \penalty0\, 3\times
+17{=}51, \penalty0\, 5\times 17{=}85, \penalty0\, 3\times 5\times
+17=255$ (la possibilité $1$ peut être écartée car $\alpha \neq 1$).
+\end{corrige}
 
 (3) Calculer les valeurs de $\alpha^i$ dans $E$ (c'est-à-dire la
 classe de $t^i$ modulo $f$) pour $i \leq 17$.
+\begin{corrige}
+On représente à chaque fois $\alpha^i$ par l'unique polynôme à
+coefficients dans $\mathbb{F}_2$ de degré $<8$ (en $\alpha$) auquel il
+est égal.  Pour $0\leq i\leq 7$, il n'y a rien de mieux à écrire que
+$\alpha^i$.  Pour $\alpha = 8$, on a bien sûr $\alpha^8 = \alpha^4 +
+\alpha^3 + \alpha^2 + 1$ d'après le polynôme $f$ lui-même.  On obtient
+les valeurs suivantes en multipliant à chaque fois par $\alpha$ et en
+remplaçant $\alpha^8$, partout où il apparaît, par l'expression
+ci-dessus.  Ceci donne :
+
+\begin{tabular}{r|l}
+$i$&$\alpha^i$\\
+\hline
+$8$&$\alpha^4 + \alpha^3 + \alpha^2 + 1$\\
+$9$&$\alpha^5 + \alpha^4 + \alpha^3 + \alpha$\\
+$10$&$\alpha^6 + \alpha^5 + \alpha^4 + \alpha^2$\\
+$11$&$\alpha^7 + \alpha^6 + \alpha^5 + \alpha^3$\\
+$12$&$\alpha^7 + \alpha^6 + \alpha^3 + \alpha^2 + 1$\\
+$13$&$\alpha^7 + \alpha^2 + \alpha + 1$\\
+$14$&$\alpha^4 + \alpha + 1$\\
+$15$&$\alpha^5 + \alpha^2 + \alpha$\\
+$16$&$\alpha^6 + \alpha^3 + \alpha^2$\\
+$17$&$\alpha^7 + \alpha^4 + \alpha^3$\\
+\end{tabular}
+
+La valeur de $\alpha^{17}$ est bien celle qui était annoncée.  (On
+pouvait aussi mener une division euclidienne pour chaque ligne, mais
+c'est très peu efficace.)
+\end{corrige}
 
 Pour permettre de vérifier les calculs, on donne le dernier résultat :
 $\alpha^{17} = \alpha^7 + \alpha^4 + \alpha^3$.  On notera aussi
@@ -243,17 +286,78 @@ $\beta$ cet élément $\alpha^{17} \in E$.
 (4) Calculer de même les valeurs de $\alpha^i$ les valeurs suivantes
 de $i$ : $34$, $51$, $68$ et $85$ (c'est-à-dire les multiples de $17$
 jusqu'à $85$ inclus) ; si l'on préfère, ce sont les premières
-puissances de $\beta$.
+puissances de $\beta$.  Pour simplifier certains calculs, on rappelle
+que $\Frob \colon x \mapsto x^2$ vérifie $\Frob(x_1 + x_2) =
+\Frob(x_1) + \Frob(x_2)$ dans $E$.
+\begin{corrige}
+Pour mener le calcul de $\alpha^{17} = \beta^2 = \Frob(\beta)$, on
+écrit $\beta = \alpha^7 + \alpha^4 + \alpha^3$, ce qui donne $\beta^2
+= \alpha^{14} + \alpha^8 + \alpha^6 = \alpha^6 + \alpha^3 + \alpha^2 +
+\alpha$.  On peut utiliser la même technique pour passer de
+$\alpha^{34} = \beta^2$ à $\alpha^{68} = \beta^4 = (\beta^2)^2$, ce
+qui donne $\alpha^{12} + \alpha^6 + \alpha^4 + \alpha^2 = \alpha^7 +
+\alpha^4 + \alpha^3 + 1$.
+
+En revanche, pour calculer $\alpha^{51} = \beta^3$ et $\alpha^{85} =
+\beta^5$, il n'y a pas mieux que de multiplier $\beta^2 = \alpha^6 +
+\alpha^3 + \alpha^2 + \alpha$ et $\beta^4 = \alpha^7 + \alpha^4 +
+\alpha^3 + 1$ respectivement par $\beta = \alpha^7 + \alpha^4 +
+\alpha^3$, développer le produit, et remplacer chaque puissance $\geq
+8$ de $\alpha$ par la valeur connue (ou effectuer une division
+euclidienne par $f$).  On obtient finalement :
+
+\begin{tabular}{r|l}
+$i$&$\alpha^i$\\
+\hline
+$17$&$\alpha^7 + \alpha^4 + \alpha^3$\\
+$34$&$\alpha^6 + \alpha^3 + \alpha^2 + \alpha$\\
+$51$&$\alpha^3 + \alpha$\\
+$68$&$\alpha^7 + \alpha^4 + \alpha^3 + 1$\\
+$85$&$\alpha^7 + \alpha^6 + \alpha^4 + \alpha^2 + \alpha$\\
+\end{tabular}
+
+La valeur de $\alpha^{85}$ est bien celle qui était annoncée.
+\end{corrige}
 
 Pour permettre de vérifier les calculs, on donne le dernier résultat :
 $\alpha^{85} = \alpha^7 + \alpha^6 + \alpha^4 + \alpha^2 + \alpha$.
 
-(5) Que vaut l'ordre multiplicatif de $\alpha$ ?  Quel est l'ordre
+(5) Que vaut l'ordre multiplicatif de $\alpha$ ?  Comment
+qualifie-t-on l'élément $\alpha$ de $E$ ?  Quel est l'ordre
 multiplicatif de $\beta = \alpha^{17}$ ?
+\begin{corrige}
+On a vu en (2) que l'ordre de $\alpha$ est un des nombres $3, 5,
+17,\penalty0 15, \penalty0 51, \penalty0 85, \penalty0 255$.  Or on a
+calculé $\alpha^i$ pour chacune des valeurs $3, 5, 17,\penalty0 15,
+\penalty0 51, \penalty0 85$, et trouvé un résultat $\neq 1$.  La seule
+possibilité qui demeure est donc $255$ : l'élément $\alpha$ est
+primitif dans $E$.
+
+Quant à l'ordre de $\beta$, puisque $\beta^i = \alpha^{17i}$ vaut $1$
+si et seulement si $17i$ est un multiple de $255$, c'est-à-dire si et
+seulement si $i$ est un multiple de $\frac{255}{17} = 15$, c'est
+exactement $15$.  (Ou si on préfère, il existe un isomorphisme $\psi
+\colon \mathbb{Z}/255\mathbb{Z} \to E^\times$ qui envoie $\bar\imath$
+sur $\alpha^i$, et l'ordre multiplicatif de $\beta = \psi(17)$ est
+donc l'ordre additif de $17$ modulo $255$, soit $\frac{255}{17} =
+15$.)
+\end{corrige}
 
-(6) Que vaut $\beta^{16}$ ?
+(6) Que vaut $\beta^{16}$ ?  Quel est le degré absolu de $\beta$ ?
+\begin{corrige}
+Puisque $\beta$ est d'ordre $15$, on a $\beta^{15} = 1$ et $\beta^{16}
+= \beta$.  Comme $\beta^2$ et $\beta^4$ et $\beta^8$ sont, pour leur
+part, différents de $1$ (toujours puisque $\beta$ est d'ordre $15$),
+le plus petit $r$ tel que $\Frob^r(\beta) := \beta^{2^r} = \beta$
+est $4$, et le degré de $\beta$ est $4$.
+\end{corrige}
 
 (7) Vérifier que $\beta^4 + \beta + 1 = 0$.
+\begin{corrige}
+On a calculé $\beta^4 = \alpha^{68} = \alpha^7 + \alpha^4 + \alpha^3 +
+1$, et c'est bien la même chose que $\beta + 1$, donc $\beta^4 + \beta
++ 1 = 0$.
+\end{corrige}
 
 On pose $g = t^4 + t + 1 \in \mathbb{F}_2[t]$, et $K =
 \mathbb{F}_2[t]/(g)$.
@@ -267,6 +371,13 @@ $\Phi(g) = 0$.
 et $\Phi(h_1 h_2) = \Phi(h_1)\, \Phi(h_2)$ pour tous $h_1,h_2 \in
 \mathbb{F}_2[t]$.  (b) Montrer que $\Phi(h) = \Phi(h')$ si $h \equiv
 h' \pmod{g}$.
+\begin{corrige}
+(a) La valeur en un point d'une somme ou d'un produit de polynômes est
+  la somme ou le produit des valeurs de ces polynômes.  (b) Si $h
+  \equiv h' \pmod{g}$ c'est que $h-h' = qg$ pour un certain $q \in
+  \mathbb{F}_2[t]$, donc $\Phi(h) - \Phi(h') = \Phi(q)\,\Phi(g)$, et
+  comme $\Phi(g) = 0$ on a $\Phi(h) = \Phi(h')$.
+\end{corrige}
 
 (9) Déduire de (8b) qu'on peut définir une application $\varphi \colon
 K \to E$ qui envoie la classe (modulo $g$) d'un polynôme $h \in
@@ -274,6 +385,18 @@ K \to E$ qui envoie la classe (modulo $g$) d'un polynôme $h \in
 $\varphi(u_1 + u_2) = \varphi(u_1) + \varphi(u_2)$ et $\varphi(u_1
 u_2) = \varphi(u_1) \, \varphi(u_2)$ pour tous $u_1,u_2 \in K$.
 Comment qualifie-t-on $\Phi$ et $\varphi$ ?
+\begin{corrige}
+Si $u \in K$, pour que la définition de $\varphi(u)$ ait un sens, il
+faut vérifier que $\Phi(h)$ ne dépend pas du polynôme $h \in
+\mathbb{F}_2[t]$ choisi pour représenter la classe $u$ modulo $g$ : or
+c'est précisément ce qui a été démontré en (8b).  Par ailleurs, la
+définition même de l'addition et de la multiplication sur $K$ fait que
+la somme ou le produit de deux classes modulo $g$ sont représentées
+par la somme ou le produit de deux polynômes représentant ces
+classes : donc (8a) implique les propriétés voulues de $\varphi$ par
+rapport à l'addition et la multiplication.  On dit que $\Phi$ et
+$\varphi$ sont des morphismes d'anneaux.
+\end{corrige}
 
 On désignera par $\gamma \in K$ (plutôt que $\bar t$) la classe de $t$
 modulo $g$.  Ainsi, on a $\varphi(\gamma) = \beta$ (puisque $\Phi(t) =
@@ -286,6 +409,38 @@ $\varphi(\gamma^i)$ et compter toutes les valeurs ainsi atteintes,
 sans oublier d'ajouter $\varphi(0)$.)  En déduire que $\varphi$ est
 injective (=deux éléments distincts de $K$ ont toujours des images
 distinctes dans $E$), et que le polynôme $g$ est irréductible.
+\begin{corrige}
+Comme $g$ est de degré $4$, l'anneau $K$ a pour cardinal $2^4 = 16$.
+Il faut prendre garde au fait qu'on ne sait pas encore que $K$ est un
+corps (à moins de vouloir vérifier autrement que $g$ est
+irréductible).
+
+Mais comme $\varphi(\gamma) = \beta$, on a $\varphi(\gamma^i) =
+\beta^i$ pour tout $i \in \mathbb{N}$.  Comme $\beta$ est
+d'ordre $15$, ceci prend $15$ valeurs distinctes.  Avec $\varphi(0) =
+0$, ceci fournit $16$ valeurs distinctes dans l'image de $\varphi$.
+Mais comme $K$ n'a pas plus que $16$ éléments, on a montré que tous
+les éléments distincts de $K$ ont des images distinctes, i.e.,
+$\varphi$ est injective.
+
+Pour conclure que $g$ est irréductible (i.e., que $K$ est bien un
+corps), on peut par exemple arguër que si $g = g_1 g_2$ avec $\deg
+g_1,\deg g_2 < 4$, alors $\Phi(g_1)\, \Phi(g_2) = \Phi(g) = 0$, mais
+$\Phi(g_i) = \varphi(\bar g_i)$ n'est pas nul car $\varphi$ est
+injective et que $g_i$ est le représentant standard de sa classe $\bar
+g_i$ modulo $g$, d'où une contradiction (car $E$ est un corps).  Si on
+préfère, on peut faire valoir le fait que la question (6) montre que
+$\beta$ appartient à l'unique corps $F$ à $16$ éléments contenu
+dans $E$, donc tout polynôme en $\beta$ est aussi dans $F$, donc
+l'image de $\Phi$, qui est aussi l'image de $\varphi$, est dans $F$,
+donc est exactement $F$ puisqu'on a trouvé qu'elle était de cardinal
+$16$ --- donc $\varphi$ est un isomorphisme de $K$ sur $F$, et comme
+$F$ est un corps, $K$ en est aussi un (donc $g$ est irréductible).
+Enfin, on pouvait simplement invoquer le fait que, comme le degré de
+$\beta$ vaut $4$ (question (6)), et que le polynôme $g$ est unitaire
+de degré $4$ et annule $\beta$, le polynôme $g$ est le polynôme
+minimal de $\beta$, donc il est irréductible.
+\end{corrige}
 
 %
 %