diff options
Diffstat (limited to 'controle-20091124.tex')
| -rw-r--r-- | controle-20091124.tex | 101 |
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} % |