path: root/controle-20111122.tex

%% 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{Frob}}
\DeclareUnicodeCharacter{00A0}{~}
%
\newif\ifcorrige
\corrigefalse
\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\\Contrôle de connaissance --- Corrigé\\{\normalsize Rappels mathématiques pour la cryptographie}}
\else
\title{INFMDI720\\Contrôle de connaissance\\{\normalsize Rappels mathématiques pour la cryptographie}}
\fi
\author{}
\date{22 novembre 2011}
\maketitle
\pretolerance=10000
\tolerance=8000

\vskip1truein\relax

\textbf{Consignes :}

Les exercices sont complètement indépendants.  Ils pourront être
traités dans un ordre quelconque, mais on demande de faire apparaître
de façon très visible dans les copies où commence chaque exercice.

Il n'est pas nécessaire de faire des réponses longues.

L'usage de tous les documents (notes de cours manuscrites ou
imprimées, livres) est autorisé.

L'usage des calculatrices électroniques est interdit.

Durée : 2h

\newpage

%
%
%

\exercice

Soit $p$ un nombre premier tel que $p \equiv 3 \pmod{4}$.

(1) Montrer que $(p-1)/2$ est impair.  Que vaut $(-1)^{(p-1)/2}$ ?

\begin{corrige}
On peut écrire $p = 3 + 4k$ avec $k \in \mathbb{Z}$, donc $p-1 = 2 +
4k$ donc $(p-1)/2 = 1 + 2k$, ce qui montre que $(p-1)/2$ est impair
(i.e., $p\equiv 1\pmod{2}$).  On a donc $(-1)^{(p-1)/2} = -1$.
\end{corrige}

(2) Si $z \in \mathbb{F}_p^\times$, que vaut $(z^2)^{(p-1)/2}$ ?  En
déduire qu'il n'existe pas de $z \in \mathbb{F}_p$ tel que $z^2 = -1$.

\begin{corrige}
Si $z \in \mathbb{F}_p^\times$, on a $(z^2)^{(p-1)/2} = z^{p-1} = 1$
dans $\mathbb{F}_p$ d'après le petit théorème de Fermat.  Il n'existe
donc pas de $z\in \mathbb{F}_p^\times$ tel que $z^2 = -1$ (car on
vient de voir que $(-1)^{(p-1)/2} = -1 \neq 1$) ; par ailleurs, si
$z=0$ on a $z^2 = 0\neq -1$ donc il n'existe pas de $z\in
\mathbb{F}_p$ tel que $z^2 = -1$.
\end{corrige}

(3) Déduire de la question précédente que le polynôme $t^2 + 1 \in
\mathbb{F}_p[t]$ est irréductible.

\begin{corrige}
Le polynôme $t^2 + 1$ étant de degré $2$, la seule façon dont il
pourrait être réductible serait qu'il le fût comme produit de deux
facteurs de degré $1$, c'est-à-dire qu'il eût deux racines.  Or la
question précédente signifie précisément que $t^2 + 1$ n'a pas de
racine dans $\mathbb{F}_p$.
\end{corrige}

On pose maintenant $E = \mathbb{F}_p[t]/(t^2+1)$.

(4) Combien d'éléments a $E$ ?  Que peut-on dire de sa structure
algébrique (est-ce un anneau, un corps...) ?  Quel autre nom (à part
« $E$ ») pourrait-on lui donner ?  Quelle est la forme générale d'un
élément de $E$ ?

\begin{corrige}
Les éléments de $E$ sont au nombre de $p^{\deg(t^2+1)} = p^2$ et se
voient comme des polynômes de degré $<2$, c'est-à-dire $\leq 1$, à
coefficients dans $\mathbb{F}_p$, autrement dit de la forme $u + v\bar
t$ avec $u,v \in \mathbb{F}_p$ (uniquement déterminés).  Par ailleurs,
comme $t^2+1$ est irréductible, on peut dire que $E$ est un corps, et
il mériterait de se noter $\mathbb{F}_{p^2}$ (c'est \emph{le} corps
fini à $p^2$ éléments).
\end{corrige}

On notera « $\sqrt{-1}$ » l'élément $\bar t$ de $E$, c'est-à-dire, la
classe modulo $t^2+1$ de l'indéterminée $t$.  (On ne cherchera pas à
donner un sens à la notation $\sqrt{\phantom{-1}}$, encore moins à
faire un lien avec les nombres réels ou complexes : on se contentera
de prendre $\sqrt{-1}$ comme une notation pour $\bar t$.)

(5) Que vaut le carré $(\sqrt{-1})^2$ de l'élément qu'on vient de
décrire ?

\begin{corrige}
Modulo $t^2 + 1$, on a $t^2 = -1$, c'est-à-dire que $(\sqrt{-1})^2 =
-1$ dans $E$.
\end{corrige}

(6) Quelles sont toutes les solutions de l'équation $z^2 = -1$
dans $E$ ?  En déduire quelle est la factorisation du polynôme $t^2 +
1$ vu, cette fois, comme un élément de $E[t]$.

\begin{corrige}
On vient de voir que $(\sqrt{-1})^2 = -1$.  On en déduit
$(-\sqrt{-1})^2 = -1$.  On a donc trouvé deux solutions, $\sqrt{-1}$
et $-\sqrt{-1}$, de l'équation $z^2 = -1$, c'est-à-dire deux racines
du polynôme $t^2 + 1 \in E[t]$.  Comme il s'agit d'un polynôme (non
nul) de degré $2$, il ne peut pas admettre strictement plus que deux
racines, donc on a bien toutes les racines : les solutions de $z^2 =
-1$ sont exactement $\sqrt{-1}$ et $-\sqrt{-1}$, et la factorisation
de $t^2+1$ dans $E[t]$ s'écrit : $t^2 + 1 =
(t-\sqrt{-1})(t+\sqrt{-1})$.
\end{corrige}

(7) Expliquer pourquoi tout élément de $E$ s'écrit de la forme
$u+v\sqrt{-1}$ avec $u,v$ deux éléments de $\mathbb{F}_p$ (uniquement
déterminés).  Donner des formules permettant de calculer la somme
$(u_1+v_1\sqrt{-1}) + (u_2+v_2\sqrt{-1})$ et le produit
$(u_1+v_1\sqrt{-1}) \cdot (u_2+v_2\sqrt{-1})$ de deux éléments de $E$,
en les mettant sous la forme $u + v\sqrt{-1}$ (on demande donc de
calculer $u$ et $v$ de la somme et du produit en fonction de
$u_1,v_1,u_2,v_2$).

\begin{corrige}
On a déjà expliqué en réponse à la question (4) que tout élément
de $E$ s'écrit de la forme $u + v\bar t$ avec $u,v \in \mathbb{F}_p$
(uniquement déterminés), et on a choisi de noter $\bar t$
comme $\sqrt{-1}$.

Pour la somme, on a $(u_1+v_1\sqrt{-1}) + (u_2+v_2\sqrt{-1}) =
(u_1+u_2) + (v_1+v_2)\sqrt{-1}$ en factorisant, c'est-à-dire qu'elle
vaut $u + v\sqrt{-1}$ avec $u = u_1+u_2$ et $v = v_1+v_2$.

Pour le produit, on a $(u_1+v_1\sqrt{-1}) \cdot (u_2+v_2\sqrt{-1}) =
u_1 u_2 + u_1 v_2 \sqrt{-1} + v_1 u_2 \sqrt{-1} + v_1 v_2
(\sqrt{-1})^2$ en développant, soit $(u_1 u_2 - v_1 v_2) + (u_1 v_2 +
v_1 u_2) \sqrt{-1}$ en utilisant $(\sqrt{-1})^2 = -1$ et en
factorisant, c'est-à-dire que ce produit vaut $u + v\sqrt{-1}$ avec $u
= u_1 u_2 - v_1 v_2$ et $v = u_1 v_2 + v_1 u_2$.
\end{corrige}

(8) Que vaut $(\sqrt{-1})^4$ ?  Déterminer $(\sqrt{-1})^r$ en
discutant suivant la valeur de l'entier $r$ modulo $4$.

\begin{corrige}
On a $(\sqrt{-1})^4 = (-1)^2 = 1$ : si on veut, l'élément $\sqrt{-1}$
de $E^\times$ est d'ordre (multiplicatif) $4$.  Par conséquent, la
valeur de $(\sqrt{-1})^r$ ne dépend que de la classe de $r$
modulo $4$.  Selon que $r$ est congru à $0$, $1$, $2$ ou $3$
modulo $4$, la valeur en question est respectivement $(\sqrt{-1})^0 =
1$, $(\sqrt{-1})^1 = \sqrt{-1}$, $(\sqrt{-1})^2 = -1$, ou
$(\sqrt{-1})^3 = -\sqrt{-1}$.
\end{corrige}

On rappelle que $\Frob \colon E \to E$ désigne l'application $x
\mapsto x^p$.

(9) D'après la question précédente, que vaut $\Frob(\sqrt{-1})$ ?

\begin{corrige}
On a $p \equiv 3 \pmod{4}$ par hypothèse, donc $\Frob(\sqrt{-1}) =
(\sqrt{-1})^p = -\sqrt{-1}$ d'après la question (8).
\end{corrige}

On rappelle pour la question suivante que $\Frob(x+y) =
\Frob(x)+\Frob(y)$ et $\Frob(xy) = \Frob(x)\,\Frob(y)$ pour tous
$x,y\in E$ (« le Frobenius est un morphisme de corps »), et aussi que
$\Frob(a) = a$ si et seulement si $a \in \mathbb{F}_p$ (petit théorème
de Fermat).

(10) Que vaut $\Frob(u + v\sqrt{-1})$ si $u,v \in \mathbb{F}_p$ ?

\begin{corrige}
On vient de voir que $\Frob(\sqrt{-1}) = -\sqrt{-1}$, et par ailleurs
$\Frob(u) = u$ et $\Frob(v) = v$ puisque $u,v \in \mathbb{F}_p$.  En
utilisant les propriétés rappelées, on a donc $\Frob(u+v\sqrt{-1}) =
u-v\sqrt{-1}$.
\end{corrige}

(11) En utilisant notamment la question précédente, montrer que l'on
a : $(u+v\sqrt{-1})^{p+1} = u^2 + v^2$ pour tous $u,v \in
\mathbb{F}_p$.

\begin{corrige}
On vient de voir que $\Frob(u+v\sqrt{-1}) = u-v\sqrt{-1}$.  On a
$(u+v\sqrt{-1})^{p+1} = (u+v\sqrt{-1}) \, (u+v\sqrt{-1})^p =
(u+v\sqrt{-1}) \, \Frob(u+v\sqrt{-1}) = (u+v\sqrt{-1}) \,
(u-v\sqrt{-1}) = u^2 + v^2$ (en utilisant les formules de la
question (7)).
\end{corrige}

(12) Rappeler pourquoi il existe un élément $g$ de $E^\times$ d'ordre
multiplicatif $p^2-1$ (on ne demande pas de démontrer ce fait, mais de
citer un théorème qui l'affirme) ; comment appelle-t-on un tel
élément ?

\begin{corrige}
Un tel élément s'appelle un élément primitif.  Il existe car le groupe
multiplicatif $E^\times$ des éléments non nuls de $E$,
d'ordre $p^2-1$, est cyclique (comme l'est le groupe multiplicatif
pour n'importe quel corps fini).
\end{corrige}

Pour $r$ entier, on définit $u_r,v_r$, éléments de $\mathbb{F}_p$, par
la formule : $u_r + v_r\sqrt{-1} = g^{r(p-1)}$, où $g$ est un élément
comme dans la question précédente.

(13) Que vaut $u_r^2 + v_r^2$ ?  Expliquer pourquoi les $(u_r,v_r)$
avec $0 \leq r \leq p$ sont deux-à-deux distincts.

\begin{corrige}
D'après (11), on a $u_r^2 + v_r^2 = (g^{r(p-1)})^{p+1} =
g^{r(p^2-1)}$.  Mais $g^{p^2-1} = 1$ puisque $g \in E^\times$.  On a
donc $u_r^2 + v_r^2 = 1$.

Si $0 \leq r \leq p$, c'est-à-dire $0 \leq r < p+1$, alors $0 \leq
r(p-1) < p^2-1$.  Puisque $g$ est d'ordre exactement $p^2-1$, les
$g^s$ pour $0 \leq s < p^2-1$ sont deux-à-deux distincts, et en
particulire les $g^{r(p-1)}$ pour $0 \leq r < p+1$ le sont.  Comme par
ailleurs $u_r$ et $v_r$ déterminent complètement $u_r + v_r
\sqrt{-1}$, les couples $(u_r,v_r)$ avec $0 \leq r \leq p$ sont
eux-mêmes deux-à-deux distincts.
\end{corrige}

(14) Réciproquement, si $u,v$ dans $\mathbb{F}_p$ vérifient $u^2 + v^2
= 1$, montrer que $u + v\sqrt{-1}$ peut s'écrire sous la forme
$g^{r(p-1)}$ (on a donc $(u,v) = (u_r,v_r)$) pour un certain $r$ qu'on
peut trouver vérifiant $0 \leq r \leq p$.

\begin{corrige}
Comme $g$ est primitif, on peut écrire $u + v\sqrt{-1} = g^s$ pour un
certain $s$ vérifiant $0 \leq s < p^2-1$.  L'hypothèse $u^2 + v^2 = 1$
assure que $(u+v\sqrt{-1})^{p+1} = 1$ (d'après (11)), c'est-à-dire
$g^{s(p+1)} = 1$.  Autrement dit, $s(p+1)$ est multiple de $p^2-1$.
Quitte à diviser par $p+1$, on voit donc que $s$ est multiple
de $p-1$, c'est-à-dire qu'on peut écrire $s = r(p-1)$, et on a alors
bien $u + v\sqrt{-1} = g^{r(p-1)}$ avec $0 \leq r < p+1$ (puiqsue $r =
\frac{s}{p-1}$).
\end{corrige}

(15) Des questions précédentes, déduire le nombre de solutions $(u,v)$
dans $\mathbb{F}_p$ de l'équation $u^2 + v^2 = 1$.

\begin{corrige}
On a montré que ces solutions étaient les $(u_r,v_r)$ avec $0\leq r
\leq p$, qui sont distinctes.  Il y en a donc $p+1$.
\end{corrige}

%
%
%
\end{document}