Test on 2011-11-22: start writing first exercise.

1 files changed, 187 insertions, 0 deletions

diff --git a/controle-20111122.tex b/controle-20111122.tex
new file mode 100644
index 0000000..bbc1c7a
--- /dev/null
+++ b/controle-20111122.tex
@@ -0,0 +1,187 @@
+%% 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
+\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\\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}
+
+%
+%
+%
+\end{document}