Finish corrections.

1 files changed, 97 insertions, 4 deletions

diff --git a/controle-20091124.tex b/controle-20091124.tex
index b527022..54f95bd 100644
--- a/controle-20091124.tex
+++ b/controle-20091124.tex
@@ -429,12 +429,12 @@ primitifs ?
   possède une factorisation non-triviale (car si $f = f_1 f_2$ avec
   $f_1,f_2$ de degré $<2$, ils seront chacun de degré $1$, donc ils
   auront nécessairement des racines).  On peut aussi préférer
-  appliquer le critère de Rabin : d'une part $f$ divise $t^9 - t$ car
-  $t^2 \equiv -t + 1 \pmod{f}$ donc $t^3 \equiv -t^2 + t \equiv -t - 1
-  \pmod{f}$, et ainsi $t^9 \equiv -t^3 - 1 \equiv t \pmod{f}$ (ce
+  appliquer le critère de Rabin : d'une part (a) $f$ divise $t^9 - t$
+  car $t^2 \equiv -t + 1 \pmod{f}$ donc $t^3 \equiv -t^2 + t \equiv -t
+  - 1 \pmod{f}$, et ainsi $t^9 \equiv -t^3 - 1 \equiv t \pmod{f}$ (ce
   n'est qu'une façon de mener le calcul, on pouvait aussi préférer
   calculer la division euclidienne de $t^9 - t$ par $f$) ; d'autre
-  part, $f$ est premier avec $t^3 - t$ car $t^3 - t \equiv t - 1
+  part, (b) $f$ est premier avec $t^3 - t$ car $t^3 - t \equiv t - 1
   \pmod{f}$ (reste de la division de $t^3 - t$ par $f$) et $f \equiv 1
   \pmod{t-1}$ (reste de la division de $f$ par $t-1$), donc
   l'algorithme d'Euclide a montré que $f$ et $t^3 - t$ sont premiers
@@ -551,6 +551,43 @@ polynôme $t$) dans $\mathbb{F}_2[t]/(t^5 + t^2 + 1)$ ?  (3) L'élément
 $\bar t$ est-il primitif dans $\mathbb{F}_2[t]/(t^5 + t^2 + 1)$ ?
 
 \begin{corrige}
+(C) (1) Le plus simple est d'appliquer le critère de Rabin : pour
+  montrer que $f = t^5 + t^2 + 1 \in \mathbb{F}_2[t]$ est
+  irréductible, il s'agit de vérifier que (a) $f$ divise $t^{32} - t$,
+  et (b) $f$ est premier avec $t^2 - t$.  Pour ce qui est de (a), on a
+  $t^5 \equiv t^2 + 1 \pmod{f}$ et on peut utiliser cette relation
+  pour calculer les puissances suivantes de $t$ modulo $f$ : $t^6
+  \equiv t^3 + t \pmod{f}$ (en multipliant par $t$) et $t^8 \equiv t^5
+  + t^3 \equiv t^3 + t^2 + 1 \pmod{f}$ (en multipliant encore), donc
+  (en élevant au carré, c'est-à-dire en appliquant le morphisme de
+  Forbenius), $t^{16} \equiv t^6 + t^4 + 1 \equiv t^4 + t^3 + t + 1
+  \pmod{f}$ (car on a vu $t^6 \equiv t^3 + t$), et en élevant de
+  nouveau au carré, $t^{32} \equiv t^8 + t^6 + t^2 + 1 \equiv (t^3 +
+  t^2 + 1) + (t^3 + t) + t^2 + 1 \equiv t \pmod{f}$, ce qui prouve
+  bien que $f$ divise $t^{32} - t$.  On pouvait aussi, bien entendu,
+  poser la division euclidienne (mais elle est un peu
+  fastidieuse\footnote{On trouve $t^{32} + t = (t^{27} + t^{24} +
+    t^{22} + t^{21} + t^{18} + t^{17} + t^{16} + t^{15} + t^{14} +
+    t^{10} + t^9 + t^7 + t^6 + t^5 + t^3 + t)(t^2+t)$.}).  Pour ce qui
+  est de (b), la division euclidienne de $f$ par $t^2 + t$ est $f =
+  (t^3 + t^2 + t)(t^2 + t) + 1$, et comme le reste est $1$, c'est le
+  pgcd souhaité et $f$ et $t^2 - t$ sont premiers entre eux.
+
+\leavevmode\hphantom{(C)} (2) Puisque $f = t^5 + t^2 + 1$ est
+irréductible, le quotient $\mathbb{F}_2[t]/(f)$ est un corps, ayant
+$2^{\deg f} = 32$ éléments, qu'on peut aussi noter $\mathbb{F}_{32}$.
+Le groupe multiplicatif $\mathbb{F}_{32}^\times$ de ses éléments non
+nuls a $31$ éléments.  Comme $31$ est premier, ses seuls diviseurs
+sont $1$ et $31$, donc les seuls ordres multiplicatifs possibles d'un
+élément non nul de $\mathbb{F}_{32}$ sont $1$ et $31$.
+
+\leavevmode\hphantom{(C)} (3) On vient de voir que l'ordre
+multiplicatif de $\bar t$ ne peut être que $1$ ou $31$.  Manifestement
+ce n'est pas $1$ car $\bar t \neq 1$ : il s'ensuit que c'est $31$, et
+$\bar t$ (comme \emph{tout} élément de $\mathbb{F}_{32}$ autre que $0$
+et $1$) est primitif.  (On pouvait aussi se fatiguer à énumérer les
+$31$ puissances $\bar t^i$ pour $i$ allant de $0$ à $30$, et vérifier
+qu'elles sont bien toutes distinctes.)
 \end{corrige}
 
 \ifcorrige\medbreak\else\relax\fi
@@ -575,6 +612,62 @@ sur $\mathbb{F}_2[t]/(\Phi_{19})$ ?  (On pourra par exemple chercher
 une racine, puis une façon d'en produire de nouvelles.)
 
 \begin{corrige}
+(D) (1) On a ${(t+1)} \penalty0\, {(t^{18}+t^{17} + \cdots + t^2+t+1)}
+  = (t^{19}+t^{18} + \cdots + t^3+t^2+t) + (t^{18}+t^{17} + \cdots +
+  t^2+t+1)$, et en regroupant par puissances de $t$ tous les termes
+  de $t^{18} + t^{18}$ à $t+t$ s'annulent, et il ne reste que $t^{19}
+  + 1$.
+
+\leavevmode\hphantom{(D)} (2) Dans $\mathbb{F}_2[t]/(t^{19}+1)$, on a
+$\bar t^{19} = 1$ puisque $t^{19} \equiv 1 \pmod{t^{19}+1}$, et si
+$0<i<19$ alors $\bar t^i \neq 1$ puisque $t^i$ a pour reste lui-même
+(il est de degré $<19$) par la division euclidienne par $t^{19}+1$.
+Donc l'ordre multiplicatif de $\bar t$ est exactement $19$.  Dans
+$\mathbb{F}_2[t]/(\Phi_{19})$, l'ordre de $\bar t$ est toujours $19$ :
+il y a plusieurs façons de justifier ce fait, par exemple :
+manifestement on a toujours $\bar t^{19} = 1$ (en effet, si $t^{19}
+\equiv 1 \pmod{t^{19}+1}$, on a aussi $t^{19} \equiv 1
+\pmod{\Phi_{19}}$ puisque $\Phi_{19}$ divise $t^{19} + 1$), et si
+$i<18$ on a $\bar t^i \neq 1$ pour les mêmes raisons de degré, et
+enfin $\bar t^{18} = \bar t^{17} + \bar t^{16} + \cdots + \bar t + 1
+\neq 1$.  On peut aussi dire : comme $\Phi_{19}(1) = 1 \neq 0$, le
+polynôme $\Phi_{19}$ n'est pas multiplie de $t+1$, donc il est premier
+avec lui (comme $t+1$ est irréductible), donc
+$\mathbb{F}_2[t]/(t^{19}+1) \cong \mathbb{F}_2[t]/(t+1) \times
+\mathbb{F}_2[t]/(\Phi_{19})$ par le théorème chinois, et comme $\bar
+t$ vaut $1$ dans $\mathbb{F}_2[t]/(t+1)$, son ordre est le même modulo
+$t^{19}+1$ et modulo $\Phi_{19}$.
+
+\leavevmode\hphantom{(D) (2)} Le nombre d'éléments de
+$\mathbb{F}_2[t]/(\Phi_{19})$ est $2^{\deg\Phi_{19}} = 2^{18} =
+262\,144$.  Puisque $\Phi_{19}$ est irréductible (comme on l'a admis),
+c'est un corps (c'est une représentation du corps
+$\mathbb{F}_{2^{18}}$ à $2^{18}$ éléments).  L'élément $\bar t$ étant
+d'ordre $19$, il est d'ordre strictement plus petit que $2^{18}-1$,
+donc cet élément n'est pas primitif.
+
+\leavevmode\hphantom{(D) (2)} Question subsidiaire : cherchons à
+factoriser $\Phi_{19}$ dans $\mathbb{F}_{2^{18}} =
+\mathbb{F}_2[t]/(\Phi_{19})$.  Pour commencer, on a $\Phi_{19}(\bar t)
+= \bar t^{18} + \bar t^{17} + \cdots + \bar t^2 + \bar t + 1 = 0$,
+donc $\Phi_{19}$ a $\bar t$ pour racine.  Par ailleurs, si $\theta$
+est une racine de $\Phi_{19}$, alors en appliquant le morphisme de
+Frobenius, on voit que $\Phi_{19}(\theta^2) = \Phi_{19}(\theta)^2 = 0$
+puisque $\Phi_{19}$ est à coefficients dans $\mathbb{F}_2$ (ou, si on
+veut, $(\theta^{18} + \cdots + \theta + 1)^2 = \theta^{36} + \cdots +
+\theta^2 + 1$).  Ceci montre que $\bar t^2$, $\bar t^4$, $\bar t^8$,
+$\bar t^{16}$ sont aussi des racines de $\Phi_{19}$, ainsi que $\bar
+t^{32} = \bar t^{13}$ (en rappelant que $\bar t$ est d'ordre $19$),
+$\bar t^{64} = \bar t^{26}$, et ainsi de suite jusqu'à $\bar
+t^{2^{17}} = \bar t^{10}$ (ensuite on retombe sur $\bar t^{2^{18}} =
+\bar t$) ; on vérifie\footnote{En fait, c'est nécessairement le cas,
+  parce que $\Phi_{19}$ ne peut pas avoir de racine multiple, mais
+  c'est une justification un peu savante.} que toutes ces puissances
+de $\bar t$ sont distinctes, c'est-à-dire, en fait, que $2$ est
+primitif modulo $19$ : donc finalement les racines de $\Phi_{19}(X)$
+dans $\mathbb{F}_{2^{18}} = \mathbb{F}_2[t]/(\Phi_{19}(t))$ sont tous
+les $\bar t^i$ pour $i$ allant de $0$ à $17$, et on a $\Phi_{19}(X) =
+(X-\bar t)(X-\bar t^2)(X-\bar t^3)\cdots (X-\bar t^{18})$.
 \end{corrige}
 
 %