summaryrefslogtreecommitdiffstats
path: root/controle-20101123.tex
blob: 787399e3bd049354c7f81a79223f8f7d40957ecd (plain)
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
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
\documentclass[12pt]{article}
\usepackage[francais]{babel}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\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{Frob}}
%
\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{23 novembre 2010}
\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.

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.

Durée : 1h30

\newpage

%
%
%

\exercice

(A) Quel entier entre $1500$ et $2500$ est congru à $36$ modulo $47$
et à $49$ modulo $53$ ?

\begin{corrige}
Trouvons d'abord une relation de Bézout entre $47$ et $53$, en
vérifiant du même coup qu'ils sont premiers entre eux.  On a les
divisions euclidiennes successives $53 = 1 \times 47 + 6$, puis $47 =
7 \times 6 + 5$, puis $6 = 1 \times 5 + 1$ : ceci montre que le pgcd
est bien $1$, et on peut ensuite écrire $1 = 1\times 6 - 1\times 5 =
8\times 6 - 1\times 47 = 8\times 53 - 9\times 47$, cette dernière
constituant la relation de Bézout recherchée.

Comme $47$ et $53$ sont premiers entre eux, le théorème chinois assure
que se donner une congruence modulo $47$ et une congruence modulo $53$
équivaut à se donner une congruence modulo $47\times 53$ ; comme
$47\times 53$ est certainement $>1000$, ceci suffira à définir un
unique entier entre $1500$ et $2500$ s'il en existe un.  On sait par
ailleurs que l'entier $36\times 8\times 53 - 49\times 9\times 47$
vérifiera les congruences recherchées ; on peut simplifier le calcul
en calculant $36\times 8 = 288 \equiv 6 \pmod{47}$ et $-49\times 9 =
-441 \equiv 36 \pmod{53}$, ce qui donne $6\times 53 + 36\times 47 =
2010$, qui vérifie les conditions demandées.
\end{corrige}

\ifcorrige\medbreak\else\relax\fi

(B) Quel est le plus petit entier naturel multiple de $9$, congru à
$6$ modulo $11$ et congru à $6$ modulo $10$ ?

\begin{corrige}
D'après le théorème chinois, être congru à $6$ modulo $10$ et $11$,
comme ceux-ci sont premiers entre eux, revient à être congru à $6$
modulo $10 \times 11 = 110$.  Cherchons maintenant une relation de
Bézout entre $110$ et $9$ : on a $110 = 12\times 9 + 2$ et $9 =
4\times 2 + 1$ donc $1 = 1\times 9 - 4\times 2 = 49\times 9 - 4\times
110$.  Le théorème chinois assure qu'être congru à $6$ modulo $110$ et
à $0$ modulo $9$ équivaut à être congru à $6\times 49\times 9 -
0\times 4\times 110$ modulo $990$ ; or $6\times 49 = 294 \equiv 74
\pmod{110}$ donc $6\times 49\times 9 \equiv 74\times 9 = 666
\pmod{990}$.  Ceci démontre que les entiers congrus à $0$ modulo $9$,
à $6$ modulo $11$ et à $6$ modulo $10$ sont ceux congrus à $666$
modulo $990$, dont le plus petit positif est $666$.
\end{corrige}

\ifcorrige\medbreak\else\relax\fi

(C) Quels sont les entiers entre $0$ et $100$ congrus à $12$ modulo $15$
et à $2$ modulo $20$ ?

\begin{corrige}
Les nombres $15$ et $20$ ne sont pas premiers entre eux : leur pgcd
vaut $5$ puisque $15 = 3\times 5$ et $20 = 4\times 5$.  Ceci étant,
les congruences $12$ modulo $15$ et $2$ modulo $20$ sont compatibles
modulo $5$ (toutes deux se réduisent sur $2$).  Vérifier ces deux
congruences revient donc simplement à être congru à $12$ modulo $15$
et à $2$ modulo $4$.  Trouvons une relation de Bézout entre $15$
et $4$ : on a $15 = 3\times 4 + 3$ et $4 = 1\times 3 + 1$ donc $1 =
1\times 4 - 1\times 3 = 4\times 4 - 1\times 15$.  Donc être congru à
$12$ modulo $15$, et à $2$ modulo $4$ (ou ce qui revient au même à $2$
modulo $20$) revient à être congru à $12\times 4\times 4 - 2\times
1\times 15 = 162$ modulo $15\times 4 = 60$.  Le seul nombre entre $0$
et $100$ vérifiant cette congruence est $42$.
\end{corrige}

\ifcorrige\medbreak\else\relax\fi

(D) Quels sont les entiers entre $0$ et $9000$ congrus à $18$
modulo $91$ et à $24$ modulo $105$ ?

\begin{corrige}
Les nombres $91$ et $105$ ne sont pas premiers entre eux : leur pgcd
est $7$ comme on le voit par exemple en appliquant l'algorithme
d'Euclide ($105 = 1\times 91+14$ puis $91 = 6\times 14 + 7$ puis $14 =
2\times 7$).  Or $18$ et $24$ ne sont pas congrus modulo $7$, donc
aucun nombre congru à $18$ modulo $91$ n'est congru à $24$
modulo $105$.
\end{corrige}

%
%
%

\exercice

On a $561 = 3\times 11\times 17$.

(1) Montrer que $n^{561} \equiv n \pmod{3}$ pour tout entier $n$, et
de même $\mathop{\mathrm{mod}} 11$ et $\mathop{\mathrm{mod}} 17$.
(Indication : la réponse à cette question doit faire intervenir le
nombre $560$ et \emph{non pas} la factorisation de $561$ donnée
ci-dessus.)

(2) En déduire que $n^{561} \equiv n \pmod{561}$ pour tout entier $n$.

\begin{corrige}
(1) On sait que $n^2 \equiv 1 \pmod{3}$ pour tout entier $n$ non
  multiple de $3$ (théorème d'Euler ou petit théorème de Fermat).
  Comme $560$ est multiple de $2$, on a \textit{a fortiori} $n^{560}
  \equiv 1 \pmod{3}$.  Ceci permet d'affirmer $n^{561} \equiv n
  \pmod{3}$ lorsque $n$ n'est pas multiple de $3$ ; or la même égalité
  vaut encore pour $n \equiv 0 \pmod{3}$ (c'est simplement $0=0$).  On
  a bien prouvé $n^{561} \equiv n \pmod{3}$ pour tout $n$.

De même : on sait que $n^{10} \equiv 1 \pmod{11}$ pour tout entier $n$
non multiple de $11$.  Comme $560$ est multiple de $10$, on a
\textit{a fortiori} $n^{560} \equiv 1 \pmod{11}$.  Ceci permet
d'affirmer $n^{561} \equiv n \pmod{11}$ pour $n$ non multiple de $11$,
et c'est encore vrai pour $n$ multiple de $11$.

De même : on sait que $n^{16} \equiv 1 \pmod{17}$ pour tout entier $n$
non multiple de $17$.  Comme $560$ est multiple de $16$, on a
\textit{a fortiori} $n^{560} \equiv 1 \pmod{17}$.  Ceci permet
d'affirmer $n^{561} \equiv n \pmod{17}$ pour $n$ non multiple de $17$,
et c'est encore vrai pour $n$ multiple de $17$.

(2) On a montré $n^{561} \equiv n \pmod{3}$ et $n^{561} \equiv n
\pmod{11}$ et $n^{561} \equiv n \pmod{17}$ pour tout entier $n$.
Comme $3,11,17$ sont premiers entre eux deux à deux, le théorème
chinois assure qu'on a alors la congruence $n^{561} \equiv n$
modulo $3\times 11\times 17 = 561$.
\end{corrige}

%
%
%

\exercice

On admet que le polynôme suivant dans $\mathbb{F}_2[t]$ est
irréductible : $f := t^8 + t^4 + t^3 + t^2 + 1$.

(1) Quel est le nombre d'éléments de $\mathbb{F}_2[t]/(f)$ ?  (Il
s'agit comme d'habitude des polynômes modulo $f$.)  Que peut-on en
dire et comment le note-t-on ?

(2a) Dans $\mathbb{F}_2[t]/(f)$, calculer les puissances $\bar t^i$ de
l'élément $\bar t$ représenté par $t$, pour $i$ allant de $0$ à $20$
inclus.  (Ici, « calculer » sous-entend qu'on demande comme d'habitude
le représentant standard, c'est-à-dire celui donné par un polynôme de
degré $<\deg f$.)

(2b) Calculer $\bar t^{34} = (\bar t^{17})^2$ et $\bar t^{68} = (\bar
t^{34})^2$ ; puis vérifier que $\bar t^{51} = \bar t^{34} \times \bar
t^{17}$ vaut $\bar t^3 + \bar t$, et que $\bar t^{85} = \bar t^{68}
\times \bar t^{17}$ vaut $\bar t^7 + \bar t^6 + \bar t^4 + \bar t^2 +
\bar t$.

(3) On a $255 = 3 \times 5 \times 17$.  Quel est l'ordre multiplicatif
de l'élément $\bar t$ ?  Est-il primitif ?

(4) Donner un élément primitif de $\mathbb{F}_2[t]/(f)$, différent de
$\bar t$ si on a répondu ci-dessus que $\bar t$ était primitif.
Combien y en a-t-il ?

(5) Quels sont les éléments $\bar\imath$ de $\mathbb{Z}/255\mathbb{Z}$
vérifiant $15\bar\imath = \bar0$ ?  Quels sont les éléments de
$\mathbb{F}_2[t]/(f)$ vérifiant $x^{16} = x$ ?  (Cette fois-ci, on ne
demande pas nécessairement de les écrire sous la forme d'un
représentant standard : n'importe quelle écriture conviendra.)
Combien y en a-t-il et que peut-on dire de l'ensemble de ces
éléments ?

(6) Trouver un élément $z$ de $\mathbb{F}_2[t]/(f)$ tel que $z^2 =
\bar t$.

\begin{corrige}
(1) Le polynôme $f$ étant irréductible, $\mathbb{F}_2[t]/(f)$ est un
  corps.  Son nombre d'éléments est $2^{\deg f} = 2^8 = 256$, et on le
  note donc généralement $\mathbb{F}_{256}$.

(2a) Pour $i < 8$, il n'y a rien de mieux à écrire pour $\bar t^i$ que
  $\bar t^i$.  On peut ensuite calculer successivement (à chaque fois
  on multiplie par $t$ et on soustrait le polynôme $f$ le cas échéant
  pour se ramener à un degré $<8$) :
\begin{itemize}
\item[$\bullet$]$\bar t^8 = \bar t^4 + \bar t^3 + \bar t^2 + 1$
\item[$\bullet$]$\bar t^9 = \bar t^5 + \bar t^4 + \bar t^3 + \bar t$
\item[$\bullet$]$\bar t^{10} = \bar t^6 + \bar t^5 + \bar t^4 + \bar t^2$
\item[$\bullet$]$\bar t^{11} = \bar t^7 + \bar t^6 + \bar t^5 + \bar t^3$
\item[$\bullet$]$\bar t^{12} = \bar t^8 + \bar t^7 + \bar t^6 + \bar
  t^4 = \bar t^7 + \bar t^6 + \bar t^3 + \bar t^2 + 1$
\item[$\bullet$]$\bar t^{13} = \bar t^8 + \bar t^7 + \bar t^4 + \bar
  t^3 + \bar t = \bar t^7 + \bar t^2 + \bar t + 1$
\item[$\bullet$]$\bar t^{14} = \bar t^8 + \bar t^3 + \bar t^2 + \bar
  t = \bar t^4 + \bar t + 1$
\item[$\bullet$]$\bar t^{15} = \bar t^5 + \bar t^2 + \bar t$
\item[$\bullet$]$\bar t^{16} = \bar t^6 + \bar t^3 + \bar t^2$
\item[$\bullet$]$\bar t^{17} = \bar t^7 + \bar t^4 + \bar t^3$
\item[$\bullet$]$\bar t^{18} = \bar t^8 + \bar t^5 + \bar t^4 = \bar
  t^5 + \bar t^3 + \bar t^2 + 1$
\item[$\bullet$]$\bar t^{19} = \bar t^6 + \bar t^4 + \bar t^3 + \bar
  t$
\item[$\bullet$]$\bar t^{20} = \bar t^7 + \bar t^5 + \bar t^4 + \bar
  t^2$
\end{itemize}

(2b) On a calculé $\bar t^{17} = \bar t^7 + \bar t^4 + \bar t^3$, on
en déduit, par application du Frobenius (c'est-à-dire en utilisant le
fait que, dans $\mathbb{F}_{256}$, on a $(u+v)^2 = u^2+v^2$), que
$\bar t^{34} = (\bar t^{17})^2 = \bar t^{14} + \bar t^8 + \bar t^6$ et
en utilisant les valeurs de $\bar t^{14}, \bar t^8$ calculées
ci-dessus, on trouve $\bar t^{34} = \bar t^6 + \bar t^3 + \bar t^2 +
\bar t$.  De même, en appliquant de nouveau le Frobenius, on trouve
$\bar t^{68} = (\bar t^{34})^2 = \bar t^{12} + \bar t^6 + \bar t^4 +
\bar t^2 = \bar t^7 + \bar t^4 + \bar t^3 + 1$.

On a alors $\bar t^{51} = \bar t^{34} \times \bar t^{17} = (\bar t^6 +
\bar t^3 + \bar t^2 + \bar t) \times (\bar t^7 + \bar t^4 + \bar t^3)
= \bar t^{13} + \bar t^8 + \bar t^7 + \bar t^4 = \bar t^3 + \bar t$.

De même, $\bar t^{85} = \bar t^{68} \times \bar t^{17} = (\bar t^7 +
\bar t^4 + \bar t^3 + 1) \times (\bar t^7 + \bar t^4 + \bar t^3) =
\bar t^{14} + \bar t^8 + \bar t^7 + \bar t^6 + \bar t^4 + \bar t^3 =
\bar t^7 + \bar t^6 + \bar t^4 + \bar t^2 + \bar t$.

(3) L'ordre de l'élément $\bar t \in \mathbb{F}_{256}^\times$ doit
diviser l'ordre de ce groupe, c'est-à-dire $255 = 3\times 5 \times
17$.  Il vaut l'un des entiers : $1$, $3$ $5$, $17$,
$3{\times}5{=}15$, $3{\times}17{=}51$, $5{\times}17{=}85$ ou
$3{\times}5{\times}17{=}255$.  Or dans les questions précédentes on a
calculé $\bar t^{15}, \bar t^{51}, \bar t^{85}$ et constaté qu'aucun
d'entre eux ne valait $1$ (et \textit{a fortiori} pas non plus $\bar
t^3$, $\bar t^5$ ou $\bar t^{17}$).  On en déduit que l'ordre de $\bar
t$ ne peut être que $255$, c'est-à-dire que $\bar t$ est primitif.
(On dit donc que le polynôme $f$ est primitif.)

Ceci prouve que le morphisme $\psi\colon \mathbb{Z}/{255}\mathbb{Z}
\to \mathbb{F}_{256}^\times$ (du groupe additif des entiers
modulo $255$ vers le groupe multiplicatif des éléments non nuls du
corps $\mathbb{F}_{256}$) défini par $\bar\imath \mapsto \bar t^i$ est
un isomorphisme.  On va s'en servir dans les questions suivantes.

(4) Les éléments primitifs, c'est-à-dire multiplicativement
générateurs, de $\mathbb{F}_{256}^\times$, correspondent, via
l'isomorphisme $\psi$, aux éléments additivement générateurs de
$\mathbb{Z}/255\mathbb{Z}$, autrement dit les classes modulo $255$ des
entiers premiers à $255$.  Il y en a $\varphi(255) = 2\times 4 \times
16 = 128$, à savoir les $\psi(\bar\imath) = \bar t^i$ avec $i$ non
multiple de $3,5,17$, et on peut donner par exemple $\bar t^2$ ou
encore $\bar t^7$.  (Remarque : pour répondre $\bar t^2$, on pouvait
aussi invoquer l'argument suivant : le Frobenius est un isomorphisme,
donc l'image par lui d'un élément primitif est encore primitif, donc
$\bar t^2, \bar t^4, \bar t^8, \ldots$ sont primitifs.)

(5) Dire que $15 \bar\imath = 0$ dans $\mathbb{Z}/255\mathbb{Z}$
signifie que $15 i$ est multiple de $255 = 15\times 17$, c'est-à-dire
que $i$ est multiple de $17$.  Autrement dit, les (quinze)
$\bar\imath$ qui vérifient ceci sont : $0$, $17$, $34$, $51$, $68$,
$85$, $102$, $119$, $136$, $153$, $170$, $187$, $204$, $221$ et $238$.

Dire que $x^{16} = x$ dans $\mathbb{F}_{256}$ signifie que soit $x=0$
(qui vérifie bien $0^{16}=0$) soit $x^{15} = 1$ (en divisant par $x$).
Dans le second cas, quitte à écrire $x = \psi(\bar\imath)$, dire
$x^{15}=1$ équivaut à $15\bar\imath = \bar 0$ dans
$\mathbb{Z}/255\mathbb{Z}$.  Or on vient de résoudre cette équation.
Les (seize) solutions de $x^{16} = x$ sont donc : $0$, $\bar t^0 = 1$,
$\bar t^{17}$, $\bar t^{34}$, $\bar t^{51}$, $\bar t^{68}$, $\bar
t^{85}$, $\bar t^{102}$, $\bar t^{119}$, $\bar t^{136}$, $\bar
t^{153}$, $\bar t^{170}$, $\bar t^{187}$, $\bar t^{204}$, $\bar
t^{221}$ et $\bar t^{238}$.

L'ensemble $\{x \in \mathbb{F}_{256} : x^{16} = x\}$ forme alors un
corps à $16$ éléments, qui est une copie de $\mathbb{F}_{16}$ dans
$\mathbb{F}_{256}$.

(6) Comme manifestement $0$ ne convient pas, on cherche $z$ tel que
$z^2 = \bar t$ sous la forme $z = \psi(\bar\jmath)$.  L'équation
devient alors $2\bar\jmath = \bar 1$ dans $\mathbb{Z}/255\mathbb{Z}$.
L'inverse de $2$ dans $\mathbb{Z}/255\mathbb{Z}$, si on ne voit pas
immédiatement que c'est $128$, peut se calculer à partir d'une
relation de Bézout entre $2$ et $255$ (soit : $255 = 127\times 2 + 1$
donc c'est $-127 \equiv 128 \pmod{255}$).  L'unique solution de $z^2 =
\bar t$ dans $\mathbb{F}_{256}$ est donc $\bar t^{128}$ (on peut
calculer que c'est $\bar t^7 + \bar t^2 + 1$).

(Autre solution de cette question : on sait qu'appliquer $8$ fois le
Frobenius à n'importe quel élément de $\mathbb{F}_{256}$ retombe sur
l'élément en question, i.e. $\Frob^8(y)=y$ pour tout $y$.  Ici, on
cherche à résoudre $\Frob(z) = \bar t$, et en appliquant $7$ fois le
Frobenius, on voit que cela équivaut à : $\Frob^8(z) = \Frob^7(\bar
t)$, soit $z = \bar t^{128}$.)
\end{corrige}

%
%
%
\end{document}