diff options
| -rw-r--r-- | controle-20141125.tex | 168 |
1 files changed, 168 insertions, 0 deletions
diff --git a/controle-20141125.tex b/controle-20141125.tex new file mode 100644 index 0000000..940e0f6 --- /dev/null +++ b/controle-20141125.tex @@ -0,0 +1,168 @@ +%% 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 :} + +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 + +% +% +% + +\renewcommand*{\thefootnote}{(\alph{footnote})} + +\exercice + +On rappelle que $1\,000\,000! = 1 \times 2 \times 3 \times \cdots +\times 1\,000\,000$ (produit de tous les entiers entre $1$ et +$1\,000\,000$). On s'intéresse au nombre $2^{1\,000\,000!}$. + +(1) Pourquoi $4$ divise-t-il $2^{1\,000\,000!}$ ? À quoi +$2^{1\,000\,000!}$ est-il congru modulo $4$ ? + +(2) Que vaut $\varphi(25)$ (où $\varphi$ désigne la fonction +indicatrice d'Euler) ? Que vaut $2^{20}$ modulo $25$ ? + +(3) Déduire de (2) la valeur de $2^{1\,000\,000!}$ modulo $25$. + +(4) En utilisant le théorème chinois, déduire de (1) et (3) la valeur +de $2^{1\,000\,000!}$ modulo $100$. + +(5) Quels sont les deux derniers chiffres de l'écriture décimale +de $2^{1\,000\,000!}$ ? + +% +% +% + +\exercice + +(1) Vérifier que le polynôme $t^2 + 1 \in \mathbb{F}_7[t]$ est +irréductible. + +On pose $F := \mathbb{F}_7[t]/(t^2 + 1)$. + +(2) Que peut-on dire de $F$ (nombre d'éléments, structure +algébrique) ? + +Dans ce qui suit, on notera $\alpha$, plutôt que $\bar t$, l'élément +de $F$ représenté par l'indéterminée $t$ (autrement dit, la classe de +$t$ modulo $t^2 + 1$). + +(3) Quel est l'ordre multiplicatif de $\alpha \in F^\times$ ? +L'élément $\alpha$ est-il primitif dans $F$ ? + +(Il pourra être utile, pour simplifier certains calculs, de se +rappeler que l'élément $6 \in \mathbb{F}_7$ s'écrit aussi $-1$.) + +(4) Que valent $(2+\alpha)^2$, $(2+\alpha)^3$, $(2+\alpha)^4$, +$(2+\alpha)^6$, $(2+\alpha)^8$, $(2+\alpha)^{12}$, $(2+\alpha)^{16}$, +$(2+\alpha)^{24}$ et $(2+\alpha)^{48}$ ? (Cette dernière valeur +devrait permettre de vérifier que les calculs ont été correctement +menés : il est donc conseillé de se demander \textit{a priori} quelle +valeur on doit nécessairement trouver.) + +(5) En utilisant les valeurs calculées à la question précédente, quel +est l'ordre multiplicatif de $2+\alpha \in F^\times$ ? L'élément +$2+\alpha$ est-il primitif dans $F$ ? + +% +% +% + +\exercice + +On admettra que le polynôme $t^7 + t + 1 \in \mathbb{F}_2[t]$ est +irréductible. + +On pose $F := \mathbb{F}_2[t]/(t^7 + t + 1)$. + +(1) Que peut-on dire de $F$ (nombre d'éléments, structure +algébrique) ? Quel est le nombre d'éléments de $F^\times$ ? + +Dans ce qui suit, on notera $\gamma$, plutôt que $\bar t$, l'élément +de $F$ représenté par l'indéterminée $t$ (autrement dit, la classe de +$t$ modulo $t^7 + t + 1$). + +(2) \emph{Sans faire aucun calcul}, que peut-on dire de l'ordre +multiplicatif de $\gamma$ dans $F^\times$ ? En remarquant que +l'entier $127$ est premier, quel est exactement l'ordre multiplicatif +de $\gamma$ dans $F^\times$ ? + +On rappelle que $\Frob\colon F\to F$ est l'application $x \mapsto +x^2$. + +(3) Calculer $\Frob^i(\gamma)$ (c'est-à-dire $\gamma^{2^i}$) pour $0 +\leq i \leq 7$. (Il peut être utile de commencer par calculer +$\gamma^7$. Par ailleurs, la valeur $\Frob^7(\gamma)$ devrait +permettre de vérifier que les calculs ont été correctement menés : il +est donc conseillé de se demander \textit{a priori} quelle valeur on +doit nécessairement trouver.) + +% +% +% +\end{document} |