path: root/controle-20091124.tex

%% 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
\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{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 donné (sauf l'exercice 3), les parties
A,B,C..., sont encore essentiellement indépendantes, mais comme elles
peuvent se ressembler et s'éclairer les unes les autres il est
recommandé de les traiter dans l'ordre.  Les questions
1,2,3... dépendent les unes des autres.

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é.

L'usage des calculatrices électroniques est interdit.  (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$.

\begin{corrige}
(A) (1) On a $10 \equiv 1 \pmod{9}$ donc $10^n \equiv 1^n \equiv
  1\pmod{9}$.  (2) Si $A = \sum_{i=0}^{+\infty} a_i 10^i$ (avec $a_i
  \in \{0,1,2,\ldots,9\}$) est l'écriture en base $10$ d'un entier
  naturel $A$, alors $A \equiv \sum_{i=0}^{+\infty} a_i \pmod{9}$
  puisque $10^i \equiv 1$ comme on vient de le voir : on a bien montré
  que $A$ est congru modulo $9$ à la somme $\sum_{i=0}^{+\infty} a_i$
  de ses chiffres décimaux.  Pour calculer le reste de la division
  euclidienne par $9$ d'un entier naturel $A$, il suffit donc de
  calculer celui de la somme de ses chiffres décimaux (ce qui peut se
  faire en itérant l'opération « somme des chiffres décimaux » jusqu'à
  obtenir un résultat à un chiffre, et remplacer $9$ par $0$ à la fin
  si nécessaire).  Remarquons qu'on peut simplifier certaines choses :
  par exemple, ignorer les $9$ dans l'écriture décimale, et remplacer
  les $8$ par des $-1$, et évidemment remplacer un nombre par la somme
  de ses chiffres décimaux à n'importe quelle étape du calcul.

\leavevmode\hphantom{(A)} (3) En appliquant ce procédé, on voit que
$745\,330\,964 \equiv\penalty-100 7+4+5+\penalty0 3+3+\penalty0 6+4
=\penalty0 32 \equiv 5 \pmod{9}$, que $390\,158\,565
\equiv\penalty-100 3+\penalty0 1+5+8+\penalty0 5+6+5 =\penalty0 33
\equiv 6 \pmod{9}$ et que $290\,797\,259\,507\,306\,660
\equiv\penalty-100 2+\penalty0 7+7+\penalty0 2+5+\penalty0
5+7+\penalty0 3+6+\penalty0 6+6 = 56 \equiv 2 \pmod{9}$.  Comme
$5\times 6 \equiv 3 \not\equiv 2 \pmod{9}$, cette « preuve par $9$ »
montre que la multiplication proposée est erronée.
\end{corrige}

\ifcorrige\medbreak\else\relax\fi

(B) (1) À quoi est congru $10^n$ modulo $11$ (en fonction
éventuellement de l'entier naturel $n$) ?  (Remarque : le nombre $10$
peut s'écrire d'une manière très simple modulo $11$...)  (2) Comment
faire pour calculer très simplement le reste de la division
euclidienne par $11$ d'un entier naturel écrit en décimal ?
(3) Montrer que la multiplication suivante est encore erronée :
$745\,330\,964 \times 390\,158\,565 = 290\,797\,259\,517\,306\,660$.

\begin{corrige}
(B) (1) On a $10 \equiv -1 \pmod{11}$ donc $10^n \equiv (-1)^n \equiv
  1\pmod{11}$, c'est-à-dire concrètement que $10^n$ vaut $+1$ ou $-1$
  modulo $11$ selon que $n$ est respectivement pair ou impair.  (2) Si
  $A = \sum_{i=0}^{+\infty} a_i 10^i$ (avec $a_i \in
  \{0,1,2,\ldots,9\}$) est l'écriture en base $10$ d'un entier
  naturel $A$, alors $A \equiv \sum_{i=0}^{+\infty} (-1)^i a_i
  \pmod{11}$ puisque $10^i \equiv (-1)^i$ comme on vient de le voir :
  on a bien montré que $A$ est congru modulo $11$ à la somme
  \emph{alternée} $\sum_{i=0}^{+\infty} (-1)^i a_i$ de ses chiffres
  décimaux, c'est-à-dire en comptant avec un $+$ tous les chiffres de
  puissance paire (unités, centaines, dizaines de milliers...) et avec
  un $-$ tous les chiffres de puissance impaire (dizaines, milliers,
  etc.).  Pour calculer le reste de la division euclidienne par $11$
  d'un entier naturel $A$, il suffit donc de calculer celui de la
  somme alternée de ses chiffres décimaux (ce qui peut se faire en
  itérant l'opération « somme alternée des chiffres décimaux », en
  n'oubliant pas les signes, jusqu'à obtenir un résultat entre $-9$ et
  $9$, et ajouter $11$ à la fin si nécessaire pour obtenir un reste
  entre $0$ et $10$ inclus).

\leavevmode\hphantom{(B)} (3) En appliquant ce procédé, on voit que
$745\,330\,964 \equiv\penalty-100 7-4+5-\penalty0 3+3+\penalty0 9-6+4
=\penalty0 15 \equiv 4 \pmod{11}$, que $390\,158\,565
\equiv\penalty-100 3-9-\penalty0 1+5-8+\penalty0 5-6+5 =\penalty0 -6
\equiv 5 \pmod{11}$ et que $290\,797\,259\,517\,306\,660
\equiv\penalty-100 -2+9+\penalty0 7-9+7-\penalty0 2+5-9+\penalty0
5-1+7-\penalty0 3-6+\penalty0 6-6 =\penalty0 8 \pmod{11}$.  Comme
$4\times 5 \equiv\penalty0 9 \not\equiv 8 \pmod{11}$, cette « preuve
  par $11$ » montre que la multiplication proposée est erronée.
\end{corrige}

\ifcorrige\medbreak\else\relax\fi

(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$.

\begin{corrige}
(C) (1) Remarquons tout d'abord que $10 \equiv 3 \pmod{7}$.  On peut
dresser de proche en proche la table suivante des puissances de $10$
modulo $7$ :

\begin{center}
\begin{tabular}{c|c|c|c|c|c|c}
$i$&$0$&$1$&$2$&$3$&$4$&$5$\\\hline
$10^i$&$1$&$3$&$2$&$-1$&$-3$&$-2$\\
\end{tabular}
\end{center}

\noindent (On a représenté $6$, $4$ et $5$ modulo $7$ par $-1$, $-3$
et $-2$ respectivement, de façon à rendre les calculs plus faciles.)
Le fait (qu'on trouve ensuite) que $10^6 \equiv 1 \pmod{7}$ était
prévu par le petit théorème de Fermat.  De façon plus générale,
$10^{6k} \equiv 1 \pmod{7}$ donc $10^{6k+i} \equiv 10^i \pmod{7}$ :
ainsi, dans la table ci-dessus, l'indice $i$ peut se lire modulo $6$.

\leavevmode\hphantom{(C)} (2) D'après ce qu'on vient d'expliquer, un
entier naturel $A = \sum_{i=0}^{+\infty} a_i 10^i$ (écrit en décimal)
est congru modulo $7$ à la somme de ses chiffres décimaux $a_i$ chacun
multiplié par une valeur dans $\{\pm 1, \pm 2, \pm 3\}$ donnée (en
fonction de $i$ modulo $6$) par la table ci-dessus : c'est-à-dire $a_0
+\penalty100 3 \times a_1 +\penalty0 2 \times a_2 -\penalty0 a_3
-\penalty0 3\times a_4 -\penalty0 2 \times a_5 +\penalty0 a_6
+\penalty0 3 \times a_7 + \cdots$.  Pour simplifier les calculs
ultérieurs, il peut être astucieux de précalculer les multiplications
par tous les chiffres décimaux possibles, c'est-à-dire de dresser le
tableau des valeurs de $a_i \times 10^i$ modulo $7$ en fonction de
$a_i$ et de $i$ :

\begin{center}
\begin{tabular}{r|c|c|c|c|c|c}
$a_i\downarrow$\textbackslash $i\rightarrow$&$0$&$1$&$2$&$3$&$4$&$5$\\\hline
$0$\rlap{, $7$}\hphantom{\textbackslash $i\rightarrow$}&$0$&$0$&$0$&$0$&$0$&$0$\\
$1$\rlap{, $8$}\hphantom{\textbackslash $i\rightarrow$}&$1$&$3$&$2$&$6$&$4$&$5$\\
$2$\rlap{, $9$}\hphantom{\textbackslash $i\rightarrow$}&$2$&$6$&$4$&$5$&$1$&$3$\\
$3$\hphantom{\textbackslash $i\rightarrow$}&$3$&$2$&$6$&$4$&$5$&$1$\\
$4$\hphantom{\textbackslash $i\rightarrow$}&$4$&$5$&$1$&$3$&$2$&$6$\\
$5$\hphantom{\textbackslash $i\rightarrow$}&$5$&$1$&$3$&$2$&$6$&$4$\\
$6$\hphantom{\textbackslash $i\rightarrow$}&$6$&$4$&$5$&$1$&$3$&$2$\\
\end{tabular}
\end{center}

\noindent Avec ce tableau, pour calculer la classe modulo $7$ de $A =
\sum_{i=0}^{+\infty} a_i 10^i$, il suffit de sommer les valeurs des
cases de chaque chiffre (la ligne étant déterminée par la valeur $a_i$
du chiffre décimal en question, et la colonne par l'exposant $i$
modulo $6$ de la puissance de $10$ utilisée).  Il s'agit simplement
d'une façon de regrouper une fois pour toutes le calcul des
multiplications par $\pm 1, \pm 2, \pm 3$, le calcul étant toujours le
même.  Pour être encore plus efficace, on peut d'ailleurs remplir le
tableau de façon « paresseuse », c'est-à-dire en ne calculant le
contenu des cases que lorsqu'on en a besoin.

\leavevmode\hphantom{(C)} (3) En appliquant ce procédé, on voit qu'on
a $617\,673\,693\,283\,947 \equiv\penalty-100 2\times 6 +\penalty1000
3\times 1 +\penalty1000 7 -\penalty0 2\times 6 -\penalty1000 3\times 7
-\penalty1000 3 +\penalty0 2\times 6 +\penalty1000 3\times 9
+\penalty1000 3 -\penalty0 2\times 2 -\penalty1000 3\times 8
-\penalty1000 3 +\penalty0 2\times 9 +\penalty1000 3\times 4
+\penalty1000 7 =\penalty-100 34 \equiv 6 \pmod{7}$ ou, en utilisant
directement le tableau ci-dessus, $\equiv 5 + 3 + 0 +\penalty0 2 + 0 +
4 +\penalty0 5 + 6 + 3 +\penalty0 3 + 4 + 4 +\penalty0 4 + 5 + 0
=\penalty-100 48 \equiv 6 \pmod{7}$.  Mais d'autre part $3^{31}$ est,
modulo $7$, congru à ($10^{31}$ donc à) $3$ puisque $31 \equiv 1 \pmod
6$ (ou si on veut, $3^{31} \equiv 3^{5\times 6 + 1} \equiv 3 \pmod{7}$
puisque $3^6 \equiv 1 \pmod{7}$).  Comme $6 \not\equiv 3$, le nombre
proposé n'est pas la valeur correcte de $3^{31}$.
\end{corrige}

%
%
%

\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 \in \mathbb{F}_3[t]$.  (2) Que peut-on
dire de $\mathbb{F}_3[t]/(t^2 + t)$ ?  (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]$.

\leavevmode\hphantom{(D)} (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 $\mathbb{F}_2[t]/(\Phi_{19})$ (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) = X^{18} + X^{17} + \cdots + X + 1$ vu comme
polynôme (en la nouvelle indéterminée $X$)
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}