diff options
| -rw-r--r-- | controle-20121127.tex | 161 |
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} % % |