1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
|
%% 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 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$.
(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$.
(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]$.
\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 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}
|
