Test for 2009-2010.

1 files changed, 196 insertions, 0 deletions

diff --git a/controle-20091124.tex b/controle-20091124.tex
new file mode 100644
index 0000000..13ac0c2
--- /dev/null
+++ b/controle-20091124.tex
@@ -0,0 +1,196 @@
+%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
+\documentclass[12pt]{article}
+\usepackage[francais]{babel}
+\usepackage[latin1]{inputenc}
+\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{Fr}}
+%
+\newif\ifcorrige
+\corrigefalse
+\newenvironment{corrige}%
+{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi%
+\smallbreak\noindent{\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{24 novembre 2009}
+\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.  À
+l'intérieur d'un exercice, les questions se suivent normalement dans
+un ordre logique, et il est vivement recommandé de les traiter dans
+cet ordre.
+
+Le sujet étant volontairement trop long pour le temps imparti, il ne
+sera pas nécessaire de traiter tous les exercices pour avoir le
+maximum des points.  Il est suggéré de prendre le temps de tous les
+lire, pour bien choisir ceux que l'on traitera.
+
+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ée.
+
+L'usage des calculatrices électroniques est interdite.  (Certains
+exercices peuvent apparaître calculatoires, mais les calculs sont
+toujours faisables à la main en un temps raisonnable, parfois au prix
+de quelques astuces.)
+
+Durée : 1h30
+
+\newpage
+
+%
+%
+%
+
+\exercice
+
+(A) (1) À quoi est congru $10^n$ modulo $9$ (en fonction
+éventuellement de l'entier naturel $n$) ?  (2) En déduire une
+démonstration de l'affirmation suivante : un entier naturel écrit en
+décimal (=base $10$) est congru modulo $9$ à la somme de ses chiffres.
+Comment faire pour calculer très simplement le reste de la division
+euclidienne par $9$ d'un entier naturel écrit en décimal ?
+(3) Montrer que la multiplication suivante est erronée :
+$745\,330\,964 \times 390\,158\,565 = 290\,797\,259\,507\,306\,660$.
+
+(B) (1) À quoi est congru $10^n$ modulo $11$ (en fonction
+éventuellement de l'entier naturel $n$) ?  (2) Comment faire pour
+calculer très simplement le reste de la division euclidienne par $11$
+d'un entier naturel écrit en décimal ?  (Remarque : le nombre $10$
+peut s'écrire d'une manière très simple modulo $11$...)  (3) Montrer
+que la multiplication suivante est encore erronée : $745\,330\,964
+\times 390\,158\,565 = 290\,797\,259\,517\,306\,660$.
+
+(C) (1) À quoi est congru $10^n$ modulo $7$, selon la valeur de $n$ ?
+(2) Proposer une méthode (moins simple que celles données en A et B,
+mais néanmoins plus économique que de poser la division) permettant de
+calculer le reste de la division euclidienne par $7$ d'un entier
+naturel écrit en décimal.  (On cherchera à se limiter à des additions
+et des multiplications par $\pm 1, \pm 2, \pm 3$.)  (3) Montrer que le
+calcul suivant est erroné : $3^{31} = 617\,673\,693\,283\,947$.
+
+%
+%
+%
+
+\exercice
+
+(A) Quel entier entre $0$ et $100$ est congru à $19$ modulo $13$ et à
+$13$ modulo $19$ ?
+
+(B) Quel entier à trois chiffres en base $10$ se termine par $23$ et
+est multiple de $19$ ?
+
+(C) Quel entier entre $0$ et $100$ est congru respectivement à
+$1,2,3,4$ modulo $2,3,5,7$ ?  (C'est-à-dire : congru à $1$ modulo $2$,
+et à $2$ modulo $3$, et à $3$ modulo $5$, et à $4$ modulo $7$.)
+
+(D) Déterminer tous les entiers entre $0$ et $2009$ congrus à $1$
+modulo chacun des nombres $7$, $11$ et $13$.  (C'est-à-dire : congrus
+à $1$ modulo $7$, et à $1$ modulo $11$, et à $1$ modulo $13$.)
+(Indication : y-t-il un nombre évident qui répond à cette condition ?)
+
+(E) Déterminer tous les entiers entre $0$ et $100\,000$ congrus à
+$192$ modulo $300$ et à $169$ modulo $305$.
+
+%
+%
+%
+
+\exercice
+
+\textit{(Les nombres $101$ et $401$ sont premiers.)}
+
+(1) Que vaut $\varphi(40\,501)$ ?
+
+(2) Quel est l'inverse de $3$ dans $\mathbb{Z}/40\,000\mathbb{Z}$ ?
+On note $s$ un entier naturel qui le représente.
+
+(Il n'est pas nécessaire d'avoir trouvé la valeur numérique de $s$
+pour pouvoir répondre aux questions suivantes.)
+
+(3) Montrer l'affirmation suivante : si $n$ est premier avec
+$40\,501$, alors $(n^3)^s \equiv n \pmod{40\,501}$.
+
+(4) Que vaut $8^s$ modulo $40\,501$ ?
+
+%
+%
+%
+
+\exercice
+
+(A) (1) Montrer que le polynôme $t^2 + t - 1 \in \mathbb{F}_3[t]$ est
+irréductible.  (2) En déduire des tables d'opération du corps
+$\mathbb{F}_9$ à $9$ éléments.  (3) Quels en sont les éléments
+primitifs ?
+
+(B) (1) Donner une racine, puis la décomposition en facteurs
+irréductibles, de $t^2 + t + 1 \in \mathbb{F}_3[t]$.  (2) Que peut-on
+dire de $\mathbb{F}_3[t]/(t^2 + t + 1)$ ?  (Plusieurs réponses
+possibles.)
+
+(C) (1) Montrer que le polynôme $t^5 + t^2 + 1 \in \mathbb{F}_2[t]$
+est irréductible.  (2) Quels sont \textit{a priori} les ordres
+multiplicatifs possibles de l'élément $\bar t$ (représenté par le
+polynôme $t$) dans $\mathbb{F}_2[t]/(t^5 + t^2 + 1)$ ?  (3) L'élément
+$\bar t$ est-il primitif dans $\mathbb{F}_2[t]/(t^5 + t^2 + 1)$ ?
+
+(D) (1) Justifier brièvement l'égalité suivante dans
+$\mathbb{F}_2[t]$ : on a $t^{19}+1 = {(t+1)} \penalty0\,
+{(t^{18}+t^{17}+t^{16} + \cdots + t^3+t^2+t+1)}$.  On appellera
+$\Phi_{19}$ le second facteur ($t^{18}+\cdots+t+1$).  On \emph{admet}
+que $\Phi_{19}$ est irréductible dans $\mathbb{F}_2[t]$.  (2) Quel est
+l'ordre multiplicatif de l'élément $\bar t$ (représent par $t$) dans
+$\mathbb{F}_2[t]/(t^{19}+1)$ ?  Dans $\mathbb{F}_2[t]/(\Phi_{19})$ ?
+Quel est le nombre d'éléments de ce dernier (on ne demande pas de
+l'écrire en décimal) ?  Est-ce un corps ?  L'élément $\bar t$ est-il
+primitif (on parle toujours dans $\mathbb{F}_2[t]/(\Phi_{19})$) ?
+Question subsidiaire, plus difficile : quelle est la décomposition en
+facteurs irréductibles du polynôme $\Phi_{19}(X)$ vu comme polynôme
+sur $\mathbb{F}_2[t]/(\Phi_{19})$ ?  (On pourra par exemple chercher
+une racine, puis une façon d'en produire de nouvelles.)
+
+%
+%
+%
+\end{document}