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