%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
\documentclass[12pt]{article}
\usepackage[francais]{babel}
\usepackage[utf8]{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}}
\DeclareUnicodeCharacter{00A0}{~}
%
\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), puis $\bar t^{27} = \bar t^2$ (car
  $\bar t^{25} = (\bar t^5)^5 = 1$), 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 multiplicatif 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}

%
%
%

\exercice

Calculer le pgcd dans $\mathbb{F}_{11}[t]$ de $t^2 - 2$ et $t^{11}-t$.
En déduire que $2$ n'est pas un carré dans $\mathbb{F}_{11}$
(c'est-à-dire qu'il n'existe pas de $\alpha \in \mathbb{F}_{11}$ tel
que $\alpha^2 = 2$ ; indication : de quels polynômes intéressants
$\alpha$ serait-il racine ?).

\begin{corrige}
On calcule les divisions euclidiennes successives : $t^{11}-t = (t^9 +
2t^7 + 4t^5 - 3t^3 + 5t)\penalty0 (t^2-2) + 9t$, puis $t^2-2 =
(5t)(9t) - 2$, le dernier reste est une constante donc le pgcd
vaut $1$.

S'il y avait un $\alpha \in \mathbb{F}_{11}$ tel que $\alpha^2 = 2$,
alors il serait racine à la fois de $t^2 - 2$ en vertu de
$\alpha^2=2$, et $t^{11} - t$ en vertu de $\alpha\in\mathbb{F}_{11}$
(et du petit théorème de Fermat).  C'est-à-dire que $t-\alpha$ serait
un facteur commu à $t^2-2$ et $t^{11}-t$, et on vient de voir qu'il
n'y en a pas.

\emph{Remarque :} Vérifier que $t^2-2$ et $t^{11}-t$ sont premiers
entre eux est une des parties du critère de Rabin pour vérifier que
$t^2-2$ est irréductible.  Ici, il n'y a pas besoin d'en faire plus :
comme $t^2-2$ n'a pas de racine, cela signifie qu'il n'a pas de
facteur de degré $1$, et comme il est de degré $2$, il est
irréductible.
\end{corrige}

%
%
%
\end{document}