diff options
| -rw-r--r-- | controle-20111122.tex | 187 |
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} |