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} |