Candidate exam for 2013-11-26.

1 files changed, 142 insertions, 0 deletions

diff --git a/controle-20131126.tex b/controle-20131126.tex
new file mode 100644
index 0000000..fc8bece
--- /dev/null
+++ b/controle-20131126.tex
@@ -0,0 +1,142 @@
+%% 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{26 novembre 2013}
+\maketitle
+\pretolerance=10000
+\tolerance=8000
+
+\vskip1truein\relax
+
+\textbf{Consignes :}
+
+Ce sujet comporte un unique exercice.  Les questions dépendent les
+unes des autres, mais ont été formulées de manière que le fait de ne
+pas savoir répondre à l'une d'entre elles, si on en admet le résultat,
+ne soit normalement pas handicapant pour la suite.  Il est cependant
+recommandé de les traiter dans l'ordre où elles sont écrites.
+
+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 : 1h30
+
+\newpage
+
+%
+%
+%
+
+\renewcommand*{\thefootnote}{(\alph{footnote})}
+
+\bigbreak\noindent\textbf{Exercice~unique.}
+
+(1) Quel est l'ordre multiplicatif de $2$ dans
+$\mathbb{F}_{11}^\times$ ?  Comment peut-on le qualifier ?
+
+(2) Expliquer pourquoi $\bar\imath \mapsto 2^i$ définit un
+isomorphisme de groupes de $\mathbb{Z}/10\mathbb{Z}$ (additif) sur
+$\mathbb{F}_{11}^\times$ (multiplicatif).
+
+(3) Montrer qu'il n'existe aucun $x \in \mathbb{F}_{11}$ tel que $x^2
+= 2$ (dans $\mathbb{F}_{11}$).
+
+(4) Montrer que le polynôme $t^2 - 2$ est irréductible dans
+$\mathbb{F}_{11}[t]$.
+
+On note $K = \mathbb{F}_{11}[t] / (t^2 - 2)$ l'anneau quotient de
+$\mathbb{F}_{11}[t]$ par le polynôme $t^2-2$.
+
+(5) Combien $K$ a-t-il d'éléments ?  Que peut-on déduire de (4) sur
+l'anneau $K$ ?
+
+Dans ce qui suit, on notera\footnote{Comme on ne parlera jamais de
+  nombres réels, et notamment pas du nombre réel noté de la même
+  manière, ceci ne devrait pas causer de confusion.} « $\sqrt{2}$ »
+(plutôt que $\bar t$) la classe de l'indéterminée $t$ dans $K$.
+
+(6) Expliquer brièvement pourquoi cette notation est raisonnable.
+Expliquer brièvement pourquoi tous les éléments de $K$ s'écrivent sous
+la forme $a + b\sqrt{2}$ avec $a,b \in \mathbb{F}_{11}$ uniquement
+déterminés.
+
+(7) Quel est l'ordre multiplicatif de $\sqrt{2}$ dans $K^\times$ ?
+
+(8) On note $\Frob\colon K \to K$ l'application $x \mapsto x^{11}$.
+Rappeler brièvement ce qu'on peut dire sur $\Frob$.
+
+(9) Que vaut $\Frob(a)$ si $a \in \mathbb{F}_{11}$ ?  Que vaut
+$\Frob(\sqrt{2})$ ?  Que vaut $\Frob(a+b\sqrt{2})$ lorsque $a,b \in
+\mathbb{F}_{11}$ ?  (On demande évidemment une réponse meilleure que
+$(a+b\sqrt{2})^{11}$...)
+
+(10) Rappeler brièvement pourquoi il existe un isomorphisme de groupes
+de $\mathbb{Z}/120\mathbb{Z}$ (additif) sur $K^\times$
+(multiplicatif).  (On ne demande pas de l'expliciter.)
+
+(11) Calculer l'inverse de $13$ dans l'anneau
+$\mathbb{Z}/120\mathbb{Z}$.  (On le représentera par un entier entre
+$0$ et $119$.)
+
+(12) Déduire de (10) et (11) que pour tout $x \in K$ il existe un
+unique $y \in K$ tel que $x = y^{13}$ (on pourra distinguer les deux
+cas $x \in K^\times$ et $x=0$).  Expliciter $y$ en fonction de $x$.
+
+(13) Calculer $(2+\sqrt{2})^r$ dans $K$ pour $r$ valant $2$ et et $4$,
+puis pour $r$ valant $11$ (il est recommandé d'utiliser la
+question (9)), $22$ et $33$, et enfin pour $r$ valant $37$.
+
+(14) En utilisant (12) et (13), résoudre l'équation $y^{13} =
+2+\sqrt{2}$ dans $K$ (en l'indéterminée $y$).
+
+%
+%
+%
+\end{document}