Possible test for 2014.

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}