summaryrefslogtreecommitdiffstats
path: root/controle-20131126.tex
blob: 8473acaccf365f066c8b3cd79168f1d1900fad44 (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
%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
\documentclass[12pt]{article}
\usepackage[francais]{babel}
\usepackage[utf8]{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}}
\DeclareUnicodeCharacter{00A0}{~}
%
\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{26 novembre 2013}
\maketitle
\pretolerance=10000
\tolerance=8000

\vskip1truein\relax

\textbf{Consignes :}

Ce sujet comporte un unique exercice.  Les questions dépendent les
unes des autres, mais ont été formulées de manière que le fait de ne
pas savoir répondre à l'une d'entre elles, si on en admet le résultat,
ne soit normalement guère handicapant pour la suite.  Il est cependant
recommandé de les traiter dans l'ordre où elles sont écrites.

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

%
%
%

\renewcommand*{\thefootnote}{(\alph{footnote})}

\bigbreak\noindent\textbf{Exercice~unique.}

(1) Quel est l'ordre multiplicatif de $2$ dans
$\mathbb{F}_{11}^\times$ ?  Comment peut-on le qualifier ?

\begin{corrige}
On calcule successivement, modulo $11$ :

\begin{tabular}{c|cccccccccccc}
$i$&$0$&$1$&$2$&$3$&$4$&$5$&$6$&$7$&$8$&$9$&$10$\\\hline
$2^i$&$1$&$2$&$4$&$8$&$5$&$10$&$9$&$7$&$3$&$6$&$1$\\
\end{tabular}

On savait d'avance qu'on aurait $2^{10} \equiv 1 \pmod{11}$ (petit
théorème de Fermat), c'est-à-dire que l'ordre (multiplicatif) de $2$
dans $\mathbb{F}_{11}^\times$ diviserait $10$.  Le fait qu'on ne soit
pas tombé sur $1$ plus tôt que $10$ signifie que l'ordre
(multiplicatif) de $2$ dans $\mathbb{F}_{11}^\times$ vaut
exactement $10$.  On peut donc qualifier $2$ de primitif modulo $11$.
\end{corrige}

(2) Expliquer pourquoi $\bar\imath \mapsto 2^i$ définit un
isomorphisme de groupes de $\mathbb{Z}/10\mathbb{Z}$ (additif) sur
$\mathbb{F}_{11}^\times$ (multiplicatif).

\begin{corrige}
Le fait d'avoir $2^{10} = 1 \in \mathbb{F}_{11}^\times$ assure qu'on a
un morphisme de groupes $\mathbb{Z}/10\mathbb{Z} \to
\mathbb{F}_{11}^\times$ défini par $\bar\imath \mapsto 2^i$ (les
puissances de $2$ sont périodiques de période $10$
dans $\mathbb{F}_{11}^\times$).  Le fait que l'ordre de $2$ soit
exactement $10$ signifie que ce morphisme est un isomorphisme (tout
élément de $\mathbb{F}_{11}^\times$ s'écrit de la forme $2^i$ pour un
$i$ uniquement déterminé modulo $10$).

On notera $\bar\psi \colon \mathbb{Z}/10\mathbb{Z} \to
\mathbb{F}_{11}^\times$ cet isomorphisme.
\end{corrige}

(3) Montrer qu'il n'existe aucun $x \in \mathbb{F}_{11}$ tel que $x^2
= 2$ (dans $\mathbb{F}_{11}$).

\begin{corrige}
Manifestement $0^2 \neq 2$, donc il s'agit de voir qu'il n'existe
aucun $x \in \mathbb{F}_{11}^\times$ tel que $x^2 = 2$.  Or si un tel
$x$ existait, il pourrait s'écrire $x = \bar\psi(\bar\imath)$ pour un
certain $\bar\imath \in \mathbb{Z}/10\mathbb{Z}$, et on aurait $
\bar\psi(2\bar\imath) = x^2 = 2 = \bar\psi(\bar 1)$, donc $2\bar\imath
= \bar 1$ dans $\mathbb{Z}/10\mathbb{Z}$ vu que $\bar\psi$ est un
isomorphisme.  Or il n'existe pas de $\bar\imath \in
\mathbb{Z}/10\mathbb{Z}$ tel que $2\bar\imath = \bar 1$ car
$2\bar\imath$ est pair (ceci a bien un sens vu que $2$ divise $10$)
alors que $\bar 1$ est impair.
\end{corrige}

(4) Montrer que le polynôme $t^2 - 2$ est irréductible dans
$\mathbb{F}_{11}[t]$.  (Il est recommandé d'utiliser la question (3).)

\begin{corrige}
Il s'agit d'un polynôme de degré $2$, donc s'il était réductible, il
aurait une racine, et on vient de voir que ce n'est pas le cas.

(On pouvait aussi appliquer le critère de Rabin : $t^2 - 2$ est
irréductible dans $\mathbb{F}_{11}[t]$ si et seulement si il divise
$t^{121} - t$ et est premier à $t^{11} - t$.  C'est toutefois beaucoup
plus fastidieux.)
\end{corrige}

On note $K = \mathbb{F}_{11}[t] / (t^2 - 2)$ l'anneau quotient de
$\mathbb{F}_{11}[t]$ par le polynôme $t^2-2$.

(5) Combien $K$ a-t-il d'éléments ?  Que peut-on déduire de (4) sur
l'anneau $K$ ?

\begin{corrige}
L'anneau $K$ a $11^2 = 121$ éléments, qui s'écrivent de façon unique
comme la classe d'un polynôme de degré $<2$, c'est-à-dire sous la
forme $a + b\bar t$ (qu'on notera ci-après $a + b\sqrt{2}$) avec
$a,b\in\mathbb{F}_{11}$.  Le fait que $t^2 - 2 \in \mathbb{F}_{11}[t]$
soit irréductible nous apprend que $K$ est un corps, c'est-à-dire
\emph{le} corps à $121$ éléments.
\end{corrige}

Dans ce qui suit, on notera\footnote{Comme on ne parlera jamais de
  nombres réels, et notamment pas du nombre réel noté de la même
  manière, ceci ne devrait pas causer de confusion.} « $\sqrt{2}$ »
(plutôt que $\bar t$) la classe de l'indéterminée $t$ dans $K$.

(6) Expliquer brièvement pourquoi cette notation est raisonnable.
Expliquer brièvement pourquoi tous les éléments de $K$ s'écrivent sous
la forme $a + b\sqrt{2}$ avec $a,b \in \mathbb{F}_{11}$ uniquement
déterminés.

\begin{corrige}
On a $(\sqrt{2})^2 = 2$ (puisque $t^2 \equiv 2 \pmod{t^2-2}$), ce qui
rend la notation raisonnable.  On a rappelé ci-dessus pourquoi tout
élément de $K$ s'écrit sous la forme $a + b\sqrt{2}$ avec
$a,b\in\mathbb{F}_{11}$ uniques.
\end{corrige}

(7) Quel est l'ordre multiplicatif de $\sqrt{2}$ dans $K^\times$ ?

\begin{corrige}
Si $r \in \mathbb{Z}$ est pair, disons $r=2i$, alors $(\sqrt{2})^r =
(\sqrt{2})^{2i} = 2^i \in K$, or on a caclulé en (1) les puissances de
$2$ dans $\mathbb{F}_{11}$ (ce sont aussi, bien sûr, les puissances de
$2$ dans $K$), en particulier ceci vaut $1$ si et seulement si $i$ est
multiple de $10$ (donc $r$ multiple de $20$).  Si $r$ est impair,
disons $r = 2i+1$, alors $(\sqrt{2})^r = 2^i \sqrt{2}$ (et d'après
l'unicité de l'écriture $a + b\sqrt{2}$, ceci ne peut jamais valoir
$1$).  On en déduit que le plus petit $r \geq 1$ pour lequel
$(\sqrt{2})^r = 1$ est $20$ : c'est-à-dire que $\sqrt{2}$ est
d'ordre $20$ dans $K^\times$.
\end{corrige}

(8) On note $\Frob\colon K \to K$ l'application $x \mapsto x^{11}$.
Rappeler brièvement ce qu'on peut dire sur $\Frob$.

\begin{corrige}
On sait que $\Frob$ (le « Frobenius ») est un morphisme d'anneau (ou
de corps) : c'est-à-dire qu'il vérifie $\Frob(x+y) = \Frob(x) +
\Frob(y)$ et $\Frob(xy) = \Frob(x)\,\Frob(y)$ pour tous $x,y \in K$.
\end{corrige}

(9) Que vaut $\Frob(a)$ si $a \in \mathbb{F}_{11}$ ?  Que vaut
$\Frob(\sqrt{2})$ ?  Que vaut $\Frob(a+b\sqrt{2})$ lorsque $a,b \in
\mathbb{F}_{11}$ ?  (On demande évidemment une réponse meilleure que
$(a+b\sqrt{2})^{11}$...)

\begin{corrige}
Si $a \in \mathbb{F}_{11}$ alors $\Frob(a) = a^{11} = a$ d'après le
petit théorème de Fermat.  Quant à $\Frob(\sqrt{2}) = \sqrt{2}^{11} =
2^5 \sqrt{2}$ (cf. réponse à la question (7)), c'est $10\sqrt{2}$
(cf. réponse à la question (1)), ou, si on préfère, $-\sqrt{2}$.
Enfin, puisque $\Frob$ est un morphisme, $\Frob(a+b\sqrt{2}) =
\Frob(a) + \Frob(b)\,\Frob(\sqrt{2})$, ce qui montre
$\Frob(a+b\sqrt{2}) = a - b\sqrt{2}$.
\end{corrige}

(10) Rappeler brièvement pourquoi il existe un isomorphisme de groupes
de $\mathbb{Z}/120\mathbb{Z}$ (additif) sur $K^\times$
(multiplicatif).  (On ne demande pas de l'expliciter.)

\begin{corrige}
Dans tout corps fini (et notamment dans $K$), il existe des éléments
primitifs, c'est-à-dire des éléments $g$ d'ordre égal à l'ordre du
groupe multiplicatif des éléments non nuls.  Ici, il existe $g$
d'ordre $\#K^\times = 120$, et alors $\bar\imath \mapsto g^i$ définit
un isomorphisme $\bar\Psi \colon \mathbb{Z}/120\mathbb{Z} \to
K^\times$ exactement comme en (2).
\end{corrige}

(11) Calculer l'inverse de $13$ dans l'anneau
$\mathbb{Z}/120\mathbb{Z}$.  (On le représentera par un entier entre
$0$ et $119$.)

\begin{corrige}
On cherche une relation de Bézout entre $13$ et $120$ : on a $120 =
9\times 13 + 3$ et $13 = 4\times 3 + 1$ donc $1 = 13 - 4\times 3$ et
$3 = 120 - 9\times 13$ donc $1 = 13 - 4\times(120-9\times 13) = 37
\times 13 - 4\times 120$.  Ceci montre que $37$ est l'inverse de $13$
modulo $120$.
\end{corrige}

(12) Déduire de (10) et (11) que pour tout $x \in K$ il existe un
unique $y \in K$ tel que $x = y^{13}$ (on pourra distinguer les deux
cas $x \in K^\times$ et $x=0$).  Expliciter $y$ en fonction de $x$.

\begin{corrige}
Si $x = 0$, chercher $y \in K$ tel que $y^{13} = 0$ a pour seule
solution $y=0$ puisque $K$ est un corps.  Considérons maintenant le
cas $x \in K^\times$ : comme $0^{13} = 0$, si $y^{13} = x$, on aura
forcément $y \neq 0$, autrement dit $y \in K^\times$.

Soit $\bar\Psi \colon \mathbb{Z}/120\mathbb{Z} \to K^\times$ un
isomorphisme de groupes (qui existe d'après (10)).  Il existe donc un
unique $\bar\imath \in \mathbb{Z}/120\mathbb{Z}$ tel que
$\bar\Psi(\bar\imath) = x$.  Par ailleurs, si $y \in K^\times$, il
existe un unique $\bar\jmath \in \mathbb{Z}/120\mathbb{Z}$ tel que
$\bar\Psi(\bar\jmath) = y$.  L'équation $x = y^{13}$ signife
$\bar\Psi(\bar\imath) = x = y^{13} = \bar\Psi(13\bar\jmath)$, donc
(puisque $\bar\Psi$ est un isomorphisme) $\bar\imath = 13\bar\jmath$
dans $\mathbb{Z}/120\mathbb{Z}$.  Mais on vient de voir que ceci
signifie $\bar\jmath = 37\bar\imath$ (car $37$ est l'inverse de $13$
dans $\mathbb{Z}/120\mathbb{Z}$) : autrement dit $y =
\bar\Psi(\bar\jmath) = \bar\Psi(37\bar\imath) = x^{37}$.

Comme on a aussi $0 = 0^{37}$, on voit que (quel que soit $x\in K$)
l'unique solution de $y^{13} = x$ (en l'indéterminée $y$) est : $y =
x^{37}$.
\end{corrige}

(13) Calculer $(2+\sqrt{2})^r$ dans $K$ pour $r$ valant $2$ et et $4$,
puis pour $r$ valant $11$ (il est recommandé d'utiliser la
question (9)), $22$ et $33$, et enfin pour $r$ valant $37$.

\begin{corrige}
On a $(2+\sqrt{2})^2 = 4 + 4\sqrt{2} + 2 = 6 + 4\sqrt{2}$.

On a $(2+\sqrt{2})^4 = (6 + 4\sqrt{2})^2 = 36 + 48\sqrt{2} + 32 = 2 +
4\sqrt{2}$ (se rappeler que les coefficients sont
dans $\mathbb{F}_{11}$).

On a $(2+\sqrt{2})^{11} = 2-\sqrt{2} = 2+10\sqrt{2}$ d'après la question (9).

On a $(2+\sqrt{2})^{22} = (6+4\sqrt{2})^{11} = 6 - 4\sqrt{2} = 6 +
7\sqrt{2}$.

On a $(2+\sqrt{2})^{33} = (2+10\sqrt{2}) \times (6+7\sqrt{2}) = 12 +
74\sqrt{2} + 140 = 9 + 8\sqrt{2}$.

Enfin, on a $(2+\sqrt{2})^{37} =(9+8\sqrt{2}) \times (2+4\sqrt{2}) =
18 + 52\sqrt{2} + 64 = 5 + 8\sqrt{2}$.
\end{corrige}

(14) En utilisant (12) et (13), résoudre l'équation $y^{13} =
2+\sqrt{2}$ dans $K$ (en l'indéterminée $y$).

\begin{corrige}
D'après ce qu'on a vu en (12), l'unique solution de $y^{13} =
2+\sqrt{2}$ vaut $(2+\sqrt{2})^{37}$, et d'après (13), ceci vaut $5 +
8\sqrt{2}$.
\end{corrige}

%
%
%
\end{document}