Start a second exercise sheet.

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}