summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--controle-20091124.tex196
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}