diff options
| -rw-r--r-- | exercices2.tex | 259 |
1 files changed, 259 insertions, 0 deletions
diff --git a/exercices2.tex b/exercices2.tex new file mode 100644 index 0000000..89f8b69 --- /dev/null +++ b/exercices2.tex @@ -0,0 +1,259 @@ +%% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it? +\documentclass[12pt]{article} +\usepackage[francais]{babel} +\usepackage[latin1]{inputenc} +\usepackage[T1]{fontenc} +\usepackage{times} +% A tribute to the worthy AMS: +\usepackage{amsmath} +\usepackage{amsfonts} +\usepackage{amssymb} +\usepackage{amsthm} +% +\usepackage{mathrsfs} +\usepackage{wasysym} +\usepackage{url} +% +\theoremstyle{definition} +\newtheorem{comcnt}{Tout} +\newcommand\exercice{% +\refstepcounter{comcnt}\bigbreak\noindent\textbf{Exercice~\thecomcnt.}} +\newcommand{\limp}{\mathrel{\Rightarrow}} +\newcommand{\liff}{\mathrel{\Longleftrightarrow}} +\newcommand{\pgcd}{\operatorname{pgcd}} +\newcommand{\ppcm}{\operatorname{ppcm}} +\newcommand{\signe}{\operatorname{signe}} +\newcommand{\tee}{\mathbin{\top}} +\newcommand{\Frob}{\operatorname{Fr}} +% +\newif\ifcorrige +\corrigetrue +\newenvironment{corrige}% +{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi% +\smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}} +{{\hbox{}\nobreak\hfill\checkmark}% +\ifcorrige\relax\else\egroup\fi\par} +% +% +% +\begin{document} +\ifcorrige +\title{INFMDI720\\Exercices --- Corrigé\\{\normalsize Rappels mathématiques pour la cryptographie}} +\else +\title{INFMDI720\\Exercices\\{\normalsize Rappels mathématiques pour la cryptographie}} +\fi +\author{} +\date{} +\maketitle +\pretolerance=10000 +\tolerance=8000 + +% +% +% + +\exercice + +Déterminer une relation de Bézout entre les polynômes $A = t^7 - t^6 + +t^4 - t + 1$ et $B = t^6 + t^5 - t^4 + t^3 + t^2 + 1$ dans +$\mathbb{F}_3[t]$. Quel est l'inverse de $\bar B$ dans +$\mathbb{F}_3[t]/(A)$ ? + +\begin{corrige} +On calcule les divisions euclidiennes successives : $t^7 - t^6 + t^4 - +t + 1 = (t+1)\penalty0 (t^6+t^5-t^4+t^3+t^2+1) + (t^4+t^3-t^2+t)$, +puis $t^6 + t^5 - t^4 + t^3 + t^2 + 1 = t^2(t^4+t^3-t^2+t) + (t^2+1)$, +puis $t^4 + t^3 - t^2 + t = (t^2+t+1)\penalty0 (t^2+1) - 1$. Le pgcd +de $A$ et $B$ est donc $1$ (ou $-1$, mais on a choisi de le prendre +unitaire). + +On calcule alors des relations $UP + VQ = D$ comme suit : + +\begin{itemize} +\item[$\bullet$] $U= -1$ ; $P= t^4+t^3-t^2+t$ ; $V= t^2+t+1$ ; $Q= + t^2+1$ ; $D= 1$ (d'après la dernière division effectuée). +\item[$\bullet$] $U= -t^2$ ; $P= t^4+t^3-t^2+t$ ; $V= 1$ ; $Q= + t^6+t^5-t^4+t^3+t^2+1$ ; $D= t^2+1$ (d'après l'avant-dernière + division effectuée). +\item[$\bullet$] $U= -t^2(t^2+t+1)-1 = -t^4-t^3-t^2-1$ ; $P= + t^4+t^3-t^2+t$ ; $V= t^2+t+1$ ; $Q= t^6+t^5-t^4+t^3+t^2+1$ ; $D= 1$ + (en remplaçant la valeur de $t^2+1$ donnée par la dernière égalité à + la place du $Q$ de l'égalité précédente). +\item[$\bullet$] $U= 1$ ; $P= t^7-t^6+t^4-t+1$ ; $V= -(t+1)$ ; $Q= + t^6+t^5-t^4+t^3+t^2+1$ ; $D= t^4+t^3-t^2+t$ (d'après la première + division effectuée). +\item[$\bullet$] $U= -t^4-t^3-t^2-1$ ; $P= t^7-t^6+t^4-t+1$ ; $V= + (t^2+t+1) - (-t^4-t^3-t^2-1)\penalty0 (t+1) = t^5-t^4-t^3-t^2-t-1$ ; + $Q= t^6+t^5-t^4+t^3+t^2+1$ ; $D= 1$ (en remplaçant la valeur de + $t^4+t^3-t^2+t$ donnée par la dernière égalité à la place du $P$ de + l'égalité précédente. +\end{itemize} + +On a donc trouvé la relation de Bézout : $(-t^4-t^3-t^2-1) \penalty0 +(t^7-t^6+t^4-t+1) + (t^5-t^4-t^3-t^2-t-1) \penalty0 +(t^6+t^5-t^4+t^3+t^2+1) = 1$. + +Ceci montre que l'inverse de $\bar B = \bar t^6+\bar t^5-\bar t^4+\bar +t^3+\bar t^2+1$ dans $\mathbb{F}_3[t]/(A)$ est $\bar t^5-\bar t^4-\bar +t^3-\bar t^2-\bar t-1$. +\end{corrige} + +% +% +% + +\exercice + +(A) On admet que le polynôme $P := t^4 + t^3 + t^2 + t + 1 \in +\mathbb{F}_3[t]$ est irréductible. Combien d'éléments a $F := +\mathbb{F}_3[t]/(P)$ ? + +(B) Quel est l'ordre (additif) de $\bar t$ dans le groupe additif +de $F$ ? + +(C) Calculer $\bar t^4$ et $\bar t^5$. Quel est l'ordre +(multiplicatif) de $\bar t$ dans le groupe multiplicatif $F^\times$ +des éléments non-nuls de $F$ ? L'élément $\bar t$ est-il primitif ? +Le polynôme $P$ est-il primitif ? + +(D) Quels sont les conjugués de $\bar t$ (=ses images successives par +le morphisme de Frobenius) ? Quel est le degré de $\bar t$ ? + +\begin{corrige} +(A) Le nombre d'éléments de $F$ est $3^{\deg P} = 3^4 = 81$ (comme le + nombre de polynômes de degré $<4$ sur $\mathbb{F}_3$). On peut donc + noter $F = \mathbb{F}_{81}$. Il s'agit d'un corps, puisque $P$ est + irréductible. + +(B) Les multiples additifs de $\bar t$ sont $0$, $\bar t$ et $2\bar t + = -\bar t$, après quoi on retombe sur $0$ (la caractéristique de $F$ + est $3$). L'ordre additif de $\bar t$, comme celui de n'importe + quel élément non nul dans un corps de caractéristique $3$, est + donc $3$. + +(C) On a $\bar t^4 = -\bar t^3 - \bar t^2 - \bar t - 1$ comme il + résulte d'une division euclidienne (évidente) de $t^4$ par $P$. Par + conséquent, $\bar t^5 = -\bar t^4 - \bar t^3 - \bar t^2 - \bar t = + 1$ (on peut aussi faire la division euclidienne de $t^5$ par $P$). + Ceci signifie que l'ordre multiplicatif de $\bar t$ divise $5$, + c'est-à-dire qu'il vaut $1$ ou $5$. Comme il ne vaut pas $1$ + (puisque $\bar t$ ne vaut pas $1$), il vaut $5$. De fait, les + puissances de $\bar t$ sont : $1$, $\bar t$, $\bar t^2$, $\bar t^3$ + et $-\bar t^3 - \bar t^2 - \bar t - 1$, après quoi on retombe + sur $1$. Comme $F^\times$ a $80$ éléments, $\bar t$ n'est pas + primitif (un élément primitif est un élément d'ordre + multiplicatif $80$). Ceci signifie précisément que le polynôme $P$ + n'est pas primitif. + +(D) Le morphisme de Frobenius est l'application $x \mapsto x^3$ + dans $F$. Les conjugués de $\bar t$, c'est-à-dire ses images + successives par le Frobenius sont : $\bar t$ lui-même, $\bar t^3$, + puis $\bar t^9 = \bar t^4 = -\bar t^3 - \bar t^2 - \bar t - 1$ (car + $\bar t^5 = 1$ à ce qu'on a vu), et ensuite on retombe sur $\bar + t^{81} = \bar t$. Le degré de $\bar t$ est $4$ (c'est forcément le + degré de $P$). +\end{corrige} + +% +% +% + +\exercice + +(A) On admet que le polynôme $P := t^4 + t + 1 \in \mathbb{F}_2[t]$ +est irréductible. Combien d'éléments a $F := \mathbb{F}_2[t]/(P)$ ? + +(B) Dresser la liste des puissances successives de $\bar t$ dans $F$. +Quel est l'ordre de $\bar t$ ? Est-il primitif ? Quel est l'inverse +de $\bar t$ ? Quels sont tous les éléments primitifs de $F$ ? Quel +est l'ordre multiplicatif de $\bar t^3$ ? Même question pour $\bar +t^5$. + +(C) Quels sont les conjugués de $\bar t$ ? Quel est son degré ? +Mêmes questions pour $\bar t^3$. Mêmes questions pour $\bar t^5$. + +(D) Quels sont les éléments de l'unique corps à $4$ éléments contenu +dans $F$ ? + +\begin{corrige} +(A) Le nombre d'éléments de $F$ est $2^{\deg P} = 2^4 = 16$ (comme le + nombre de polynômes de degré $<4$ sur $\mathbb{F}_2$). On peut donc + noter $F = \mathbb{F}_{16}$. Il s'agit d'un corps, puisque $P$ est + irréductible. + +(B) On calcule successivement en multipliant par $t$ et en se + rappelant que $t^4 \equiv t+1 \pmod{P}$ : + +\begin{tabular}{r|l} +$i$&$\bar t^i$\\\hline +$0$&$1$\\ +$1$&$\bar t$\\ +$2$&$\bar t^2$\\ +$3$&$\bar t^3$\\ +$4$&$\bar t^4 = \bar t+1$\\ +$5$&$\bar t^2+\bar t$\\ +$6$&$\bar t^3+\bar t^2$\\ +$7$&$\bar t^4 + \bar t^3 = \bar t^3+\bar t+1$\\ +$8$&$\bar t^4+\bar t^2+\bar t = \bar t^2+1$\\ +$9$&$\bar t^3+\bar t$\\ +$10$&$\bar t^4+\bar t^2 = \bar t^2+\bar t+1$\\ +$11$&$\bar t^3+\bar t^2+\bar t$\\ +$12$&$\bar t^4+\bar t^3+\bar t^2 = \bar t^3+\bar t^2+\bar t+1$\\ +$13$&$\bar t^4+\bar t^3+\bar t^2+\bar t = \bar t^3+\bar t^2+1$\\ +$14$&$\bar t^4+\bar t^3+\bar t = \bar t^3+1$\\\hline +$15$&$\bar t^4+\bar t = 1$\\ +\end{tabular} + +L'ordre de $\bar t$ est donc $15$, il est primitif puisque $\#F^\times += \#F-1 = 15$, tous les éléments non-nuls de $F$ ont été listés +ci-dessus et on a même, plus précisément, établi un isomorphisme de +groupes $(\mathbb{Z}/15\mathbb{Z}) \to F^\times$ par $\bar\imath +\mapsto \bar t^i$. Cet isomorphisme permet de répondre facilement aux +questions suivantes : l'inverse de $\bar t$ est celui qui correspond à +l'opposé de $1$, soit $\bar t^{14} = \bar t^3+1$. Les éléments +primitifs sont ceux qui correspondent aux générateurs de +$\mathbb{Z}/15\mathbb{Z}$ (c'est-à-dire les classes des nombres +premiers avec $15$, soit $\bar 1$, $\bar 2$, $\bar 4$, $\bar 7$, $\bar +8$, $\bar{11}$, $\bar{13}$, $\bar{14}$), donc $\bar t$, $\bar t^2$, +$\bar t^4 = \bar t+1$, $\bar t^7 = \bar t^3+\bar t+1$, $\bar t^8 = +\bar t^2+1$, $\bar t^{11} = \bar t^3+\bar t^2+\bar t$, $\bar t^{13} = +\bar t^3+\bar t^2+1$ et $\bar t^{14} = \bar t^3+1$. L'ordre +(multiplicatif) de $\bar t^3$ dans $F^\times$ est le même que l'ordre +(additif) de $3$ dans $\mathbb{Z}/15\mathbb{Z}$, soit $5$, et de même +l'ordre multiplicatif de $\bar t^5$ dans $F^\times$ est $3$. + +(C) Le morphisme de Frobenius est l'application $x \mapsto x^2$ +dans $F$. Les conjugués de $\bar t$, c'est-à-dire ses images +successives par le Frobenius sont : $\bar t$ lui-même, $\bar t^2$, +$\bar t^4 = \bar t+1$, $\bar t^8 = \bar t^2+1$ après quoi on retombe +sur $\bar t^{16} = \bar t$. Le degré de $\bar t$ est $4$ (c'est +forcément le degré de $P$). Pour ce qui est du degré de $\bar t^3$, +ses images successives par le Frobenius sont : $\bar t^3$ lui-même, +$\bar t^6 = \bar t^3+\bar t^2$, $\bar t^{12} = \bar t^3+\bar t^2+\bar +t+1$ et $\bar t^{24} = \bar t^9 = \bar t^3+\bar t$, après quoi on +retombe sur $\bar t^{48} = \bar t^3$ ; donc le degré de $\bar t^3$ est +également $4$. Enfin, pour calculer le degré de $\bar t^5$, on a ses +images successives qui sont $\bar t^5 = \bar t^2+\bar t$ lui-même et +$\bar t^{10} = \bar t^2+\bar t+1$, puis $\bar t^{20} = \bar t^5$, donc +il n'y a que deux conjugués (en comptant $\bar t^5$ lui-même), et son +degré est $2$. + +(D) On sait que $\mathbb{F}_4$ est contenu dans $F = \mathbb{F}_{16}$ +car $16$ est une puissance de $4$, et on sait qu'alors $\mathbb{F}_4 = +\{x\in F : x^4=x\}$. Une façon de trouver ces éléments est de +réécrire $x^4 = x$ comme $(x^2)^2 = x$ (on retombe sur $x$ après deux +applications du Frobenius : ou encore, le degré de $x$ est $1$ +ou $2$) ; les éléments vérifiant ceci sont $0$ et $1$, bien sûr, et +aussi $\bar t^5 = \bar t^2+\bar t$ comme on vient de le voir, et +forcément $\bar t^5 + 1 = \bar t^2+\bar t+1$ (puisqu'un corps est +stable ar addition). Une autre façon de résoudre $x^4 = x$ est de le +réécrire comme $x=0$ ou bien $x^3 = 1$, c'est-à-dire qu'il s'agit de +$0$ et des éléments d'ordre divisant $3$, donc, d'après l'isomorphisme +déjà déterminé, $\bar t^5 = \bar t^2+\bar t$ et $\bar t^{10} = \bar +t^2+\bar t+1$. +\end{corrige} + +% +% +% +\end{document} |