summaryrefslogtreecommitdiffstats
path: root/exercices2.tex
blob: 7cee36234b73f7daf823ea6e8ee92007c327c2a2 (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
%% 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{Fr}}
\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\\Exercices --- Corrigé\\{\normalsize Rappels mathématiques pour la cryptographie}}
\else
\title{INFMDI720\\Exercices\\{\normalsize Rappels mathématiques pour la cryptographie}}
\fi
\author{}
\date{}
\maketitle
\pretolerance=10000
\tolerance=8000

%
%
%

\exercice

Déterminer une relation de Bézout entre les polynômes $A = t^7 - t^6 +
t^4 - t + 1$ et $B = t^6 + t^5 - t^4 + t^3 + t^2 + 1$ dans
$\mathbb{F}_3[t]$.  Quel est l'inverse de $\bar B$ dans
$\mathbb{F}_3[t]/(A)$ ?

\begin{corrige}
On calcule les divisions euclidiennes successives : $t^7 - t^6 + t^4 -
t + 1 = (t+1)\penalty0 (t^6+t^5-t^4+t^3+t^2+1) + (t^4+t^3-t^2+t)$,
puis $t^6 + t^5 - t^4 + t^3 + t^2 + 1 = t^2(t^4+t^3-t^2+t) + (t^2+1)$,
puis $t^4 + t^3 - t^2 + t = (t^2+t+1)\penalty0 (t^2+1) - 1$.  Le pgcd
de $A$ et $B$ est donc $1$ (ou $-1$, mais on a choisi de le prendre
unitaire).

On calcule alors des relations $UP + VQ = D$ comme suit :

\begin{itemize}
\item[$\bullet$] $U= -1$ ; $P= t^4+t^3-t^2+t$ ; $V= t^2+t+1$ ; $Q=
  t^2+1$ ; $D= 1$ (d'après la dernière division effectuée).
\item[$\bullet$] $U= -t^2$ ; $P= t^4+t^3-t^2+t$ ; $V= 1$ ; $Q=
  t^6+t^5-t^4+t^3+t^2+1$ ; $D= t^2+1$ (d'après l'avant-dernière
  division effectuée).
\item[$\bullet$] $U= -t^2(t^2+t+1)-1 = -t^4-t^3-t^2-1$ ; $P=
  t^4+t^3-t^2+t$ ; $V= t^2+t+1$ ; $Q= t^6+t^5-t^4+t^3+t^2+1$ ; $D= 1$
  (en remplaçant la valeur de $t^2+1$ donnée par la dernière égalité à
  la place du $Q$ de l'égalité précédente).
\item[$\bullet$] $U= 1$ ; $P= t^7-t^6+t^4-t+1$ ; $V= -(t+1)$ ; $Q=
  t^6+t^5-t^4+t^3+t^2+1$ ; $D= t^4+t^3-t^2+t$ (d'après la première
  division effectuée).
\item[$\bullet$] $U= -t^4-t^3-t^2-1$ ; $P= t^7-t^6+t^4-t+1$ ; $V=
  (t^2+t+1) - (-t^4-t^3-t^2-1)\penalty0 (t+1) = t^5-t^4-t^3-t^2-t-1$ ;
  $Q= t^6+t^5-t^4+t^3+t^2+1$ ; $D= 1$ (en remplaçant la valeur de
  $t^4+t^3-t^2+t$ donnée par la dernière égalité à la place du $P$ de
  l'égalité précédente.
\end{itemize}

On a donc trouvé la relation de Bézout : $(-t^4-t^3-t^2-1) \penalty0
(t^7-t^6+t^4-t+1) + (t^5-t^4-t^3-t^2-t-1) \penalty0
(t^6+t^5-t^4+t^3+t^2+1) = 1$.

Ceci montre que l'inverse de $\bar B = \bar t^6+\bar t^5-\bar t^4+\bar
t^3+\bar t^2+1$ dans $\mathbb{F}_3[t]/(A)$ est $\bar t^5-\bar t^4-\bar
t^3-\bar t^2-\bar t-1$.
\end{corrige}

%
%
%

\exercice

(A) On admet que le polynôme $P := t^4 + t^3 + t^2 + t + 1 \in
\mathbb{F}_3[t]$ est irréductible.  Combien d'éléments a $F :=
\mathbb{F}_3[t]/(P)$ ?

(B) Quel est l'ordre (additif) de $\bar t$ dans le groupe additif
de $F$ ?

(C) Calculer $\bar t^4$ et $\bar t^5$.  Quel est l'ordre
(multiplicatif) de $\bar t$ dans le groupe multiplicatif $F^\times$
des éléments non-nuls de $F$ ?  L'élément $\bar t$ est-il primitif ?
Le polynôme $P$ est-il primitif ?

(D) Quels sont les conjugués de $\bar t$ (=ses images successives par
le morphisme de Frobenius) ?  Quel est le degré de $\bar t$ ?

\begin{corrige}
(A) Le nombre d'éléments de $F$ est $3^{\deg P} = 3^4 = 81$ (comme le
  nombre de polynômes de degré $<4$ sur $\mathbb{F}_3$).  On peut donc
  noter $F = \mathbb{F}_{81}$.  Il s'agit d'un corps, puisque $P$ est
  irréductible.

(B) Les multiples additifs de $\bar t$ sont $0$, $\bar t$ et $2\bar t
  = -\bar t$, après quoi on retombe sur $0$ (la caractéristique de $F$
  est $3$).  L'ordre additif de $\bar t$, comme celui de n'importe
  quel élément non nul dans un corps de caractéristique $3$, est
  donc $3$.

(C) On a $\bar t^4 = -\bar t^3 - \bar t^2 - \bar t - 1$ comme il
  résulte d'une division euclidienne (évidente) de $t^4$ par $P$.  Par
  conséquent, $\bar t^5 = -\bar t^4 - \bar t^3 - \bar t^2 - \bar t =
  1$ (on peut aussi faire la division euclidienne de $t^5$ par $P$).
  Ceci signifie que l'ordre multiplicatif de $\bar t$ divise $5$,
  c'est-à-dire qu'il vaut $1$ ou $5$.  Comme il ne vaut pas $1$
  (puisque $\bar t$ ne vaut pas $1$), il vaut $5$.  De fait, les
  puissances de $\bar t$ sont : $1$, $\bar t$, $\bar t^2$, $\bar t^3$
  et $-\bar t^3 - \bar t^2 - \bar t - 1$, après quoi on retombe
  sur $1$.  Comme $F^\times$ a $80$ éléments, $\bar t$ n'est pas
  primitif (un élément primitif est un élément d'ordre
  multiplicatif $80$).  Ceci signifie précisément que le polynôme $P$
  n'est pas primitif.

(D) Le morphisme de Frobenius est l'application $x \mapsto x^3$
  dans $F$.  Les conjugués de $\bar t$, c'est-à-dire ses images
  successives par le Frobenius sont : $\bar t$ lui-même, $\bar t^3$,
  puis $\bar t^9 = \bar t^4 = -\bar t^3 - \bar t^2 - \bar t - 1$ (car
  $\bar t^5 = 1$ à ce qu'on a vu), et ensuite on retombe sur $\bar
  t^{81} = \bar t$.  Le degré de $\bar t$ est $4$ (c'est forcément le
  degré de $P$).
\end{corrige}

%
%
%

\exercice

(A) On admet que le polynôme $P := t^4 + t + 1 \in \mathbb{F}_2[t]$
est irréductible.  Combien d'éléments a $F := \mathbb{F}_2[t]/(P)$ ?

(B) Dresser la liste des puissances successives de $\bar t$ dans $F$.
Quel est l'ordre de $\bar t$ ?  Est-il primitif ?  Quel est l'inverse
de $\bar t$ ?  Quels sont tous les éléments primitifs de $F$ ?  Quel
est l'ordre multiplicatif de $\bar t^3$ ?  Même question pour $\bar
t^5$.

(C) Quels sont les conjugués de $\bar t$ ?  Quel est son degré ?
Mêmes questions pour $\bar t^3$.  Mêmes questions pour $\bar t^5$.

(D) Quels sont les éléments de l'unique corps à $4$ éléments contenu
dans $F$ ?

\begin{corrige}
(A) Le nombre d'éléments de $F$ est $2^{\deg P} = 2^4 = 16$ (comme le
  nombre de polynômes de degré $<4$ sur $\mathbb{F}_2$).  On peut donc
  noter $F = \mathbb{F}_{16}$.  Il s'agit d'un corps, puisque $P$ est
  irréductible.

(B) On calcule successivement en multipliant par $t$ et en se
  rappelant que $t^4 \equiv t+1 \pmod{P}$ :

\begin{tabular}{r|l}
$i$&$\bar t^i$\\\hline
$0$&$1$\\
$1$&$\bar t$\\
$2$&$\bar t^2$\\
$3$&$\bar t^3$\\
$4$&$\bar t^4 = \bar t+1$\\
$5$&$\bar t^2+\bar t$\\
$6$&$\bar t^3+\bar t^2$\\
$7$&$\bar t^4 + \bar t^3 = \bar t^3+\bar t+1$\\
$8$&$\bar t^4+\bar t^2+\bar t = \bar t^2+1$\\
$9$&$\bar t^3+\bar t$\\
$10$&$\bar t^4+\bar t^2 = \bar t^2+\bar t+1$\\
$11$&$\bar t^3+\bar t^2+\bar t$\\
$12$&$\bar t^4+\bar t^3+\bar t^2 = \bar t^3+\bar t^2+\bar t+1$\\
$13$&$\bar t^4+\bar t^3+\bar t^2+\bar t = \bar t^3+\bar t^2+1$\\
$14$&$\bar t^4+\bar t^3+\bar t = \bar t^3+1$\\\hline
$15$&$\bar t^4+\bar t = 1$\\
\end{tabular}

L'ordre de $\bar t$ est donc $15$, il est primitif puisque $\#F^\times
= \#F-1 = 15$, tous les éléments non-nuls de $F$ ont été listés
ci-dessus et on a même, plus précisément, établi un isomorphisme de
groupes $(\mathbb{Z}/15\mathbb{Z}) \to F^\times$ par $\bar\imath
\mapsto \bar t^i$.  Cet isomorphisme permet de répondre facilement aux
questions suivantes : l'inverse de $\bar t$ est celui qui correspond à
l'opposé de $1$, soit $\bar t^{14} = \bar t^3+1$.  Les éléments
primitifs sont ceux qui correspondent aux générateurs de
$\mathbb{Z}/15\mathbb{Z}$ (c'est-à-dire les classes des nombres
premiers avec $15$, soit $\bar 1$, $\bar 2$, $\bar 4$, $\bar 7$, $\bar
8$, $\bar{11}$, $\bar{13}$, $\bar{14}$), donc $\bar t$, $\bar t^2$,
$\bar t^4 = \bar t+1$, $\bar t^7 = \bar t^3+\bar t+1$, $\bar t^8 =
\bar t^2+1$, $\bar t^{11} = \bar t^3+\bar t^2+\bar t$, $\bar t^{13} =
\bar t^3+\bar t^2+1$ et $\bar t^{14} = \bar t^3+1$.  L'ordre
(multiplicatif) de $\bar t^3$ dans $F^\times$ est le même que l'ordre
(additif) de $3$ dans $\mathbb{Z}/15\mathbb{Z}$, soit $5$, et de même
l'ordre multiplicatif de $\bar t^5$ dans $F^\times$ est $3$.

(C) Le morphisme de Frobenius est l'application $x \mapsto x^2$
dans $F$.  Les conjugués de $\bar t$, c'est-à-dire ses images
successives par le Frobenius sont : $\bar t$ lui-même, $\bar t^2$,
$\bar t^4 = \bar t+1$, $\bar t^8 = \bar t^2+1$ après quoi on retombe
sur $\bar t^{16} = \bar t$.  Le degré de $\bar t$ est $4$ (c'est
forcément le degré de $P$).  Pour ce qui est du degré de $\bar t^3$,
ses images successives par le Frobenius sont : $\bar t^3$ lui-même,
$\bar t^6 = \bar t^3+\bar t^2$, $\bar t^{12} = \bar t^3+\bar t^2+\bar
t+1$ et $\bar t^{24} = \bar t^9 = \bar t^3+\bar t$, après quoi on
retombe sur $\bar t^{48} = \bar t^3$ ; donc le degré de $\bar t^3$ est
également $4$.  Enfin, pour calculer le degré de $\bar t^5$, on a ses
images successives qui sont $\bar t^5 = \bar t^2+\bar t$ lui-même et
$\bar t^{10} = \bar t^2+\bar t+1$, puis $\bar t^{20} = \bar t^5$, donc
il n'y a que deux conjugués (en comptant $\bar t^5$ lui-même), et son
degré est $2$.

(D) On sait que $\mathbb{F}_4$ est contenu dans $F = \mathbb{F}_{16}$
car $16$ est une puissance de $4$, et on sait qu'alors $\mathbb{F}_4 =
\{x\in F : x^4=x\}$.  Une façon de trouver ces éléments est de
réécrire $x^4 = x$ comme $(x^2)^2 = x$ (on retombe sur $x$ après deux
applications du Frobenius : ou encore, le degré de $x$ est $1$
ou $2$) ; les éléments vérifiant ceci sont $0$ et $1$, bien sûr, et
aussi $\bar t^5 = \bar t^2+\bar t$ comme on vient de le voir, et
forcément $\bar t^5 + 1 = \bar t^2+\bar t+1$ (puisqu'un corps est
stable ar addition).  Une autre façon de résoudre $x^4 = x$ est de le
réécrire comme $x=0$ ou bien $x^3 = 1$, c'est-à-dire qu'il s'agit de
$0$ et des éléments d'ordre divisant $3$, donc, d'après l'isomorphisme
déjà déterminé, $\bar t^5 = \bar t^2+\bar t$ et $\bar t^{10} = \bar
t^2+\bar t+1$.
\end{corrige}

%
%
%

\exercice

Calculer le pgcd dans $\mathbb{F}_{11}[t]$ de $t^2 - 2$ et $t^{11}-t$.
En déduire que $2$ n'est pas un carré dans $\mathbb{F}_{11}$
(c'est-à-dire qu'il n'existe pas de $\alpha \in \mathbb{F}_{11}$ tel
que $\alpha^2 = 2$ ; indication : de quels polynômes intéressants
$\alpha$ serait-il racine ?).

\begin{corrige}
On calcule les divisions euclidiennes successives : $t^{11}-t = (t^9 +
2t^7 + 4t^5 - 3t^3 + 5t)\penalty0 (t^2-2) + 9t$, puis $t^2-2 =
(5t)(9t) - 2$, le dernier reste est une constante donc le pgcd
vaut $1$.

S'il y avait un $\alpha \in \mathbb{F}_{11}$ tel que $\alpha^2 = 2$,
alors il serait racine à la fois de $t^2 - 2$ en vertu de
$\alpha^2=2$, et $t^{11} - t$ en vertu de $\alpha\in\mathbb{F}_{11}$
(et du petit théorème de Fermat).  C'est-à-dire que $t-\alpha$ serait
un facteur commu à $t^2-2$ et $t^{11}-t$, et on vient de voir qu'il
n'y en a pas.

\emph{Remarque :} Vérifier que $t^2-2$ et $t^{11}-t$ sont premiers
entre eux est une des parties du critère de Rabin pour vérifier que
$t^2-2$ est irréductible.  Ici, il n'y a pas besoin d'en faire plus :
comme $t^2-2$ n'a pas de racine, cela signifie qu'il n'a pas de
facteur de degré $1$, et comme il est de degré $2$, il est
irréductible.
\end{corrige}

%
%
%
\end{document}