diff options
| -rw-r--r-- | controle-20101123.tex | 132 |
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} + % % % |