Slightly alter, and solve exercise 3.

1 files changed, 128 insertions, 4 deletions

diff --git a/controle-20101123.tex b/controle-20101123.tex
index c884f88..1e8452c 100644
--- a/controle-20101123.tex
+++ b/controle-20101123.tex
@@ -24,7 +24,7 @@
 \newcommand{\ppcm}{\operatorname{ppcm}}
 \newcommand{\signe}{\operatorname{signe}}
 \newcommand{\tee}{\mathbin{\top}}
-\newcommand{\Frob}{\operatorname{Fr}}
+\newcommand{\Frob}{\operatorname{Frob}}
 %
 \newif\ifcorrige
 \corrigetrue
@@ -207,15 +207,21 @@ irréductible : $f := t^8 + t^4 + t^3 + t^2 + 1$.
 (1) Quel est le nombre d'éléments de $\mathbb{F}_2[t]/(f)$ ?  Que
 peut-on en dire et comment a-t-on l'habitude de le noter ?
 
-(2) Dans $\mathbb{F}_2[t]/(f)$, calculer les puissances $\bar t^i$ de
+(2a) Dans $\mathbb{F}_2[t]/(f)$, calculer les puissances $\bar t^i$ de
 l'élément $\bar t$ représenté par $t$, pour $i$ allant de $0$ à $20$
 inclus.  (Ici, « calculer » sous-entend qu'on demande comme d'habitude
 le représentant standard, c'est-à-dire celui donné par un polynôme de
 degré $<\deg f$.)
 
+(2b) Calculer $\bar t^{34} = (\bar t^{17})^2$ et $\bar t^{68} = (\bar
+t^{34})^2$ ; puis vérifier que $\bar t^{51} = \bar t^{34} \times \bar
+t^{17}$ vaut $\bar t^3 + \bar t$, et que $\bar t^{85} = \bar t^{68}
+\times \bar t^{17}$ vaut $\bar t^7 + \bar t^6 + \bar t^4 + \bar t^2 +
+\bar t$.
+
 (3) On a $255 = 3 \times 5 \times 17$.  L'élément $\bar t$ est-il
 primitif ?  Si non, quel est son ordre multiplicatif ?  Si oui,
-comment qualifie-t-on le polynôme $f$ du fait de cette propriété ?
+comment qualifie-t-on le polynôme $f$ ?
 
 (4) Donner un élément primitif de $\mathbb{F}_2[t]/(f)$, différent de
 $\bar t$ si on a répondu ci-dessus que $\bar t$ était primitif.
@@ -225,13 +231,131 @@ Combien y en a-t-il ?
 vérifiant $15\bar\imath = \bar0$ ?  Quels sont les éléments de
 $\mathbb{F}_2[t]/(f)$ vérifiant $x^{16} = x$ ?  (Cette fois-ci, on ne
 demande pas nécessairement de les écrire sous la forme d'un
-représentant standard : n'importe quelle autre écriture conviendra.)
+représentant standard : n'importe quelle écriture conviendra.)
 Combien y en a-t-il et que peut-on dire de l'ensemble de ces
 éléments ?
 
 (6) Trouver un élément $z$ de $\mathbb{F}_2[t]/(f)$ tel que $z^2 =
 \bar t$.
 
+\begin{corrige}
+(1) Le polynôme $f$ étant irréductible, $\mathbb{F}_2[t]/(f)$ est un
+  corps.  Son nombre d'éléments est $2^{\deg f} = 2^8 = 256$, et on le
+  note donc généralement $\mathbb{F}_{256}$.
+
+(2a) Pour $i < 8$, il n'y a rien de mieux à écrire pour $\bar t^i$ que
+  $\bar t^i$.  On peut ensuite calculer successivement (à chaque fois
+  on multiplie par $t$ et on soustrait le polynôme $f$ le cas échéant
+  pour se ramener à un degré $<8$) :
+\begin{itemize}
+\item[$\bullet$]$\bar t^8 = \bar t^4 + \bar t^3 + \bar t^2 + 1$
+\item[$\bullet$]$\bar t^9 = \bar t^5 + \bar t^4 + \bar t^3 + \bar t$
+\item[$\bullet$]$\bar t^{10} = \bar t^6 + \bar t^5 + \bar t^4 + \bar t^2$
+\item[$\bullet$]$\bar t^{11} = \bar t^7 + \bar t^6 + \bar t^5 + \bar t^3$
+\item[$\bullet$]$\bar t^{12} = \bar t^8 + \bar t^7 + \bar t^6 + \bar
+  t^4 = \bar t^7 + \bar t^6 + \bar t^3 + \bar t^2 + 1$
+\item[$\bullet$]$\bar t^{13} = \bar t^8 + \bar t^7 + \bar t^4 + \bar
+  t^3 + \bar t = \bar t^7 + \bar t^2 + \bar t + 1$
+\item[$\bullet$]$\bar t^{14} = \bar t^8 + \bar t^3 + \bar t^2 + \bar
+  t = \bar t^4 + \bar t + 1$
+\item[$\bullet$]$\bar t^{15} = \bar t^5 + \bar t^2 + \bar t$
+\item[$\bullet$]$\bar t^{16} = \bar t^6 + \bar t^3 + \bar t^2$
+\item[$\bullet$]$\bar t^{17} = \bar t^7 + \bar t^4 + \bar t^3$
+\item[$\bullet$]$\bar t^{18} = \bar t^8 + \bar t^5 + \bar t^4 = \bar
+  t^5 + \bar t^3 + \bar t^2 + 1$
+\item[$\bullet$]$\bar t^{19} = \bar t^6 + \bar t^4 + \bar t^3 + \bar
+  t$
+\item[$\bullet$]$\bar t^{20} = \bar t^7 + \bar t^5 + \bar t^4 + \bar
+  t^2$
+\end{itemize}
+
+(2b) On a calculé $\bar t^{17} = \bar t^7 + \bar t^4 + \bar t^3$, on
+en déduit, par application du Frobenius (c'est-à-dire en utilisant le
+fait que, dans $\mathbb{F}_{256}$, on a $(u+v)^2 = u^2+v^2$), que
+$\bar t^{34} = (\bar t^{17})^2 = \bar t^{14} + \bar t^8 + \bar t^6$ et
+en utilisant les valeurs de $\bar t^{14}, \bar t^8$ calculées
+ci-dessus, on trouve $\bar t^{34} = \bar t^6 + \bar t^3 + \bar t^2 +
+\bar t$.  De même, en appliquant de nouveau le Frobenius, on trouve
+$\bar t^{68} = (\bar t^{34})^2 = \bar t^{12} + \bar t^6 + \bar t^4 +
+\bar t^2 = \bar t^7 + \bar t^4 + \bar t^3 + 1$.
+
+On a alors $\bar t^{51} = \bar t^{34} \times \bar t^{17} = (\bar t^6 +
+\bar t^3 + \bar t^2 + \bar t) \times (\bar t^7 + \bar t^4 + \bar t^3)
+= \bar t^{13} + \bar t^8 + \bar t^7 + \bar t^4 = \bar t^3 + \bar t$.
+
+De même, $\bar t^{85} = \bar t^{68} \times \bar t^{17} = (\bar t^7 +
+\bar t^4 + \bar t^3 + 1) \times (\bar t^7 + \bar t^4 + \bar t^3) =
+\bar t^{14} + \bar t^8 + \bar t^7 + \bar t^6 + \bar t^4 + \bar t^3 =
+\bar t^7 + \bar t^6 + \bar t^4 + \bar t^2 + \bar t$.
+
+(3) L'ordre de l'élément $\bar t \in \mathbb{F}_{256}^\times$ doit
+diviser l'ordre de ce groupe, c'est-à-dire $255 = 3\times 5 \times
+17$.  Il vaut l'un des entiers : $1$, $3$ $5$, $17$,
+$3{\times}5{=}15$, $3{\times}17{=}51$, $5{\times}17{=}85$ ou
+$3{\times}5{\times}17{=}255$.  Or dans les questions précédentes on a
+calculé $\bar t^{15}, \bar t^{51}, \bar t^{85}$ et constaté qu'aucun
+d'entre eux ne valait $1$ (et \textit{a fortiori} pas non plus $\bar
+t^3$, $\bar t^5$ ou $\bar t^{17}$).  On en déduit que l'ordre de $\bar
+t$ ne peut être que $255$, c'est-à-dire que $\bar t$ est primitif.  On
+dit donc que le polynôme $f$ est primitif.
+
+Ceci prouve que le morphisme $\psi\colon \mathbb{Z}/{255}\mathbb{Z}
+\to \mathbb{F}_{256}^\times$ (du groupe additif des entiers
+modulo $255$ vers le groupe multiplicatif des éléments non nuls du
+corps $\mathbb{F}_{256}$) défini par $\bar\imath \mapsto \bar t^i$ est
+un isomorphisme.  On va s'en servir dans les questions suivantes.
+
+(4) Les éléments primitifs, c'est-à-dire multiplicativement
+générateurs, de $\mathbb{F}_{256}^\times$, correspondent, via
+l'isomorphisme $\psi$, aux éléments additivement générateurs de
+$\mathbb{Z}/255\mathbb{Z}$, autrement dit les classes modulo $255$ des
+entiers premiers à $255$.  Il y en a $\varphi(255) = 2\times 4 \times
+16 = 128$, à savoir les $\psi(\bar\imath) = \bar t^i$ avec $i$ non
+multiple de $3,5,17$, et on peut donner par exemple $\bar t^2$ ou
+encore $\bar t^7$.  (Remarque : pour répondre $\bar t^2$, on pouvait
+aussi invoquer l'argument suivant : le Frobenius est un isomorphisme,
+donc l'image par lui d'un élément primitif est encore primitif, donc
+$\bar t^2, \bar t^4, \bar t^8, \ldots$ sont primitifs.)
+
+(5) Dire que $15 \bar\imath = 0$ dans $\mathbb{Z}/255\mathbb{Z}$
+signifie que $15 i$ est multiple de $255 = 15\times 17$, c'est-à-dire
+que $i$ est multiple de $17$.  Autrement dit, les (quinze)
+$\bar\imath$ qui vérifient ceci sont : $0$, $17$, $34$, $51$, $68$,
+$85$, $102$, $119$, $136$, $153$, $170$, $187$, $204$, $221$ et $238$.
+
+Dire que $x^{16} = x$ dans $\mathbb{F}_{256}$ signifie que soit $x=0$
+(qui vérifie bien $0^{16}=0$) soit $x^{15} = 1$ (en divisant par $x$).
+Dans le second cas, quitte à écrire $x = \psi(\bar\imath)$, dire
+$x^{15}=1$ équivaut à $15\bar\imath = \bar 0$ dans
+$\mathbb{Z}/255\mathbb{Z}$.  Or on vient de résoudre cette équation.
+Les (seize) solutions de $x^{16} = x$ sont donc : $0$, $\bar t^0 = 1$,
+$\bar t^{17}$, $\bar t^{34}$, $\bar t^{51}$, $\bar t^{68}$, $\bar
+t^{85}$, $\bar t^{102}$, $\bar t^{119}$, $\bar t^{136}$, $\bar
+t^{153}$, $\bar t^{170}$, $\bar t^{187}$, $\bar t^{204}$, $\bar
+t^{221}$ et $\bar t^{238}$.
+
+L'ensemble $\{x \in \mathbb{F}_{256} : x^{16} = x\}$ forme alors un
+corps à $16$ éléments, qui est une copie de $\mathbb{F}_{16}$ dans
+$\mathbb{F}_{256}$.
+
+(6) Comme manifestement $0$ ne convient pas, on cherche $z$ tel que
+$z^2 = \bar t$ sous la forme $z = \psi(\bar\jmath)$.  L'équation
+devient alors $2\bar\jmath = \bar 1$ dans $\mathbb{Z}/255\mathbb{Z}$.
+L'inverse de $2$ dans $\mathbb{Z}/255\mathbb{Z}$, si on ne voit pas
+immédiatement que c'est $128$, peut se calculer à partir d'une
+relation de Bézout entre $2$ et $255$ (soit : $255 = 127\times 2 + 1$
+donc c'est $-127 \equiv 128 \pmod{255}$).  L'unique solution de $z^2 =
+\bar t$ dans $\mathbb{F}_{256}$ est donc $\bar t^{128}$ (on peut
+calculer que c'est $\bar t^7 + \bar t^2 + 1$).
+
+(Autre solution de cette question : on sait qu'appliquer $8$ fois le
+Frobenius à n'importe quel élément de $\mathbb{F}_{256}$ retombe sur
+l'élément en question, i.e. $\Frob^8(y)=y$ pour tout $y$.  Ici, on
+cherche à résoudre $\Frob(z) = \bar t$, et en appliquant $7$ fois le
+Frobenius, on voit que cela équivaut à : $\Frob^8(z) = \Frob^7(\bar
+t)$, soit $z = \bar t^{128}$.)
+\end{corrige}
+
 %
 %
 %