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}