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