summaryrefslogtreecommitdiffstats
path: root/exercices.tex
blob: d5128205b73bf607b9064161efb6119d3b7b7bf2 (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
%% 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

(A) Quel entier entre $0$ et $100$ est congru à $19$ modulo $13$ et à
$13$ modulo $19$ ?

\begin{corrige}
(A) Commençons par trouver un entier qui convient.  On pourrait se
  rendre compte que $19+13 = 32$ convient pour des raisons de
  symétrie.  Pour procéder de façon plus systématique, cherchons une
  relation de Bézout entre $19$ et $13$, qui sont visiblement premiers
  entre eux (et ceci va de toute façon le confirmer) : on a $19 = 1\times 13 +
  6$ puis $13 = 2\times 6 + 1$ donc le pgcd est bien $1$, et on a $1 =
  13 - 2\times 6 = 3\times 13 - 2\times 19$.  Ainsi, d'après un
  résultat du cours (version « effective » du théorème chinois), un
  nombre congru à $19$ (soit $6$) modulo $13$ et à $13$ modulo $19$
  est donné par $3 \times 13 \times 13 - 2 \times 19 \times 6$ : ceci
  vaut $279$, mais pour simplifier les calculs on pouvait calculer
  $3\times 13 \equiv 1 \pmod{19}$ et $-2 \times 6 \equiv 1 \pmod{13}$,
  donc il reste $13 + 19 = 32$.  En tout état de cause, comme $13$ et
  $19$ sont premiers entre eux, les nombres congrus à $x$ modulo $13$
  et à $y$ modulo $19$, quels que soient $x$ et $y$ entiers, forment
  une unique classe de congruence modulo $13 \times 19 = 247$ (qu'il
  n'était pas vraiment nécessaire de calculer, seul importe que ce
  soit $>100$, ce qui est évident), donc dès qu'on a trouvé un nombre
  vérifiant les congruences demandées (en l'occurrence $32$), on sait
  que les autres sont les nombres qui lui sont congrus modulo $13
  \times 19$, et en particulier il n'y en a pas d'autre entre $0$
  et $100$.
\end{corrige}

\ifcorrige\medbreak\else\relax\fi

(B) Quel entier à trois chiffres en base $10$ se termine par $23$ et
est multiple de $19$ ?

\begin{corrige}
(B) Se terminer par $23$ en base $10$ signifie être congru à $23$
  modulo $100$.  Cherchons une relation de Bézout entre $100$ et $19$
  qui sont premiers entre eux : on a $100 = 5\times 19 + 5$ et $19 =
  3\times 5 + 4$ et $5 = 1\times 4 + 1$ donc $1 = 5 - 4 = 4 \times 5 - 19 = 4
  \times 100 - 21 \times 19$.  Ainsi, d'après un résultat du cours
  (version « effective » du théorème chinois), un nombre congru à $23$
  modulo $100$ et à $0$ modulo $19$ (i.e., divisible par $19$) est
  donné par $- 21 \times 19 \times 23$ : ceci vaut $-9177$, mais pour
  simplifier les calculs on pouvait calculer $-21\times 23 \equiv -83
  \equiv 17 \pmod{100}$ et ainsi $- 21 \times 19 \times 23 \equiv 17
  \times 19 = 323 \pmod{1900}$.  Le nombre $323$ répond aux conditions
  demandées, et comme tout les entiers congrus à $23$ modulo $100$ et
  à $0$ modulo $19$ forment une unique classe de congruence
  modulo $1900$, on a trouvé le seul nombre à trois chiffres.
\end{corrige}

\ifcorrige\medbreak\else\relax\fi

(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$.)

\begin{corrige}
(C) Les nombres $2,3,5,7$ sont premiers entre eux deux à deux.
  Commençons par trouver des solutions à deux congruences
  simultanées : comme les nombres sont assez petits, il est plus
  simple de le faire par tâtonnement : par exemple, $5$ est congru à
  $1$ modulo $2$ et à $2$ modulo $3$, cela se trouve immédiatement en
  parcourant les entiers de $0$ à $5$ ou plus astucieusement ceux qui
  vérifient une des deux congruences pour chercher ceux qui vérifient
  l'autre.  Comme on va vouloir mettre ensuite ensemble deux
  congruences de ce genre, il vaut mieux les trouver de même taille
  et, si possible, vérifiant une relation de Bézout simple : le plus
  économique est donc de mettre $2$ avec $7$ et $3$ avec $5$, ce qui a
  le bon goût que $1\times 15 - 1\times 14 = 1$ est une relation de Bézout évidente
  entre $3\times 5$ et $2\times 7$.  Par tâtonnement, on trouve que
  $11$ (et exactement les nombres de sa classe modulo $14$) est congru
  à $1$ modulo $2$ et à $4$ modulo $7$, et que $8$ (et exactement les
  nombres de sa classe modulo $15$) est congru à $2$ modulo $3$ et à
  $3$ modulo $5$.  Avec la relation de Bézout $1\times 15 - 1\times 14
  = 1$, toujours en appliquant la même version « effective » du
  théorème chinois, on voit que les entiers vérifiant les quatre
  congruences demandées sont exactement la classe de $1\times 15\times
  11 - 1\times 14\times 8 = 53$ modulo $15 \times 14 = 210$, donc le
  seul entre $0$ et $100$ est $53$.
\end{corrige}

\ifcorrige\medbreak\else\relax\fi

(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 ?)

\begin{corrige}
(D) Comme le suggère l'indication, il y a un nombre évident congru à
  $1$ modulo $7$ et $11$ et $13$ à la fois, c'est $1$ lui-même.  Le
  théorème chinois assure que, comme $7$ et $11$ et $13$ sont premiers
  entre eux deux à deux, les entiers congrus à $1$ modulo chacun d'eux
  forment une classe de congruence modulo $7 \times 11 \times 13 =
  1001$.  Les nombres entre $0$ et $2009$ vérifiant les congruences
  demandées sont donc : $1$, $1002$ et $2003$.
\end{corrige}

\ifcorrige\medbreak\else\relax\fi

(E) Déterminer tous les entiers entre $0$ et $100\,000$ congrus à
$192$ modulo $300$ et à $169$ modulo $305$.

\begin{corrige}
(E) Un entier congru à $192$ modulo $300$ est (comme $5|300$) congru à
  $192 \equiv 2$ modulo $5$, et un entier congru à $169$ modulo $305$
  est (comme $5|305$) congru à $169 \equiv 4$ modulo $5$.  Comme $2
  \not\equiv 4 \pmod{5}$, il n'existe \emph{aucun} entier vérifiant
  les deux congruences demandées.
\end{corrige}

%
%
%

\exercice

(A) Pour chaque élément de $\mathbb{Z}/18\mathbb{Z}$, calculer son
ordre additif et, si cela a un sens, son ordre multiplicatif.  Quels
sont les entiers primitifs modulo $18$ ?

(B) Dresser la table d'un isomorphisme entre le groupe additif
$\mathbb{Z}/n\mathbb{Z}$ (pour un $n$ à déterminer) et le groupe
multiplicatif $(\mathbb{Z}/18\mathbb{Z})^\times$.

(C) Que vaut $7^{333\,333}$ modulo $18$ ?  Que vaut $5^{6\,000\,004}$
modulo $18$ ?

\begin{corrige}
(A)\strut\par{\footnotesize
\begin{tabular}{r|c|c}
&add.&mult.\\\hline
$\bar 0$&$1$&---\\
$\bar 1$&$18$&$1$\\
$\bar 2$&$9$&---\\
$\bar 3$&$6$&---\\
$\bar 4$&$9$&---\\
$\bar 5$&$18$&$6$\\
$\bar 6$&$3$&---\\
$\bar 7$&$18$&$3$\\
$\bar 8$&$9$&---\\
$\bar 9$&$2$&---\\
$\bar{10}$&$9$&---\\
$\bar{11}$&$18$&$6$\\
$\bar{12}$&$3$&---\\
$\bar{13}$&$18$&$3$\\
$\bar{14}$&$9$&---\\
$\bar{15}$&$6$&---\\
$\bar{16}$&$9$&---\\
$\bar{17}$&$18$&$2$\\
\end{tabular}
\par}

Il existe donc des éléments primitifs, il en existe
$\varphi(\varphi(18)) = \varphi(6) = 2$, à savoir $\bar 5$ et
$\bar{11}$.  (Les entiers primitifs modulo $18$ sont donc ceux congrus
à $5$ ou $11$ modulo $18$.)

(B) Une fois choisi un élément primitif, disons $g = \bar 5$,
l'isomorphisme $\mathbb{Z}/6\mathbb{Z} \to
(\mathbb{Z}/18\mathbb{Z})^\times$ est donné par $\bar k \mapsto g^k$,
soit ici :

\begin{tabular}{c|cccccc}
$\bar k \in \mathbb{Z}/6\mathbb{Z}$&$\bar 0$&$\bar 1$&$\bar 2$&$\bar 3$&$\bar 4$&$\bar 5$\\\hline
$g^k \in (\mathbb{Z}/18\mathbb{Z})^\times$&$\bar 1$&$\bar 5$&$\bar 7$&$\bar{17}$&$\bar{13}$&$\bar{11}$\\
\end{tabular}

(C) On vient de voir que l'ordre de $\bar 7$ dans
$(\mathbb{Z}/18\mathbb{Z})^\times$ vaut $3$, donc $7^{3k} \equiv 1
\pmod{18}$ pour tout $k$ et en particulier pour $k = 111\,111$, de
sorte que $7^{333\,333} \equiv 1 \pmod{18}$.  Pour ce qui est de
$5^{6\,000\,004}$, il suffit de chercher la valeur en regard de
$6\,000\,004$ modulo $6$ dans le tableau ci-dessus : on a $5^6 \equiv
1 \pmod{18}$ donc $5^{6\,000\,000} \equiv 1$ donc $5^{6\,000\,004}
\equiv 5^4 \equiv 13 \pmod{18}$.
\end{corrige}

%
%
%

\exercice

(A) Calculer $\varphi(3\,125)$.  Que vaut $2^{5\,000\,000}$
modulo $3\,125$ ?

(B) Que vaut $2^{5\,000\,000}$ modulo $32$ ?

(C) Sachant que $293\times 32 - 3\times 3\,125 = 1$, quels sont les
cinq derniers chiffres en base $10$ de $2^{5\,000\,000}$ ?

\begin{corrige}
(A) On a $3\,125 = 5^5$ donc $\varphi(3\,125) = 4\times 5^4 = 2\,500$.
  Comme $2$ est premier avec $3\,125$, le théorème d'Euler entraîne
  que $2^{2\,500} \equiv 1 \pmod{3\,125}$, donc $2^{5\,000\,000}
  \equiv 1 \pmod{3\,125}$ (puisque $2\,500\,|\,5\,000\,000$).

(B) (Attention à ne pas chercher à appliquer le théorème d'Euler !
  $2$ n'est pas du tout premier avec $32$...)  On a $32 = 2^5$ donc
  $32 | 2^{5\,000\,000}$, c'est-à-dire que $2^{5\,000\,000} \equiv 0
  \pmod{32}$.

(C) Trouver les cinq derniers chiffres de $2^{5\,000\,000}$ en
  base $10$ revient à calculer ce nombre modulo $100\,000 = 10^5 = 2^5
  \times 5^5 = 32 \times 3\,125$.  On vient de le calculer modulo $32$
  (il vaut $0$) et modulo $3\,125$ (il vaut $1$).  Le théorème chinois
  assure donc que $2^{5\,000\,000}$ est, modulo $100\,000$, l'unique
  classe de congruence possible qui vaut $0$ modulo $32$ et $1$
  modulo $3\,125$.  C'est donc $293\times 32 = 1 + 3\times 3\,125 =
  9\,376$.  Les cinq derniers chiffres de $2^{5\,000\,000}$ en
  base $10$ sont donc : $09376$.
\end{corrige}

%
%
%

\exercice

Les nombres $593$ et $1\,187$ sont premiers.

(A) Expliquer brièvement pourquoi, si $b^2 = \bar 1$ avec $b \in
\mathbb{Z}/1187\mathbb{Z}$ alors $b = \bar 1$ ou $b = -\bar 1$
(indication : factoriser $b^2 - \bar 1$).

(B) Quelles sont les valeurs possibles de $a^{593}$ modulo $1\,187$
(pour $a$ un entier quelconque) ?

(C) Montrer que $a^{593} \equiv -1 \pmod{1\,187}$ si et seulement si
$a$ est primitif modulo $1\,187$ \emph{ou} $a \equiv -1
\pmod{1\,187}$.

\begin{corrige}
(A) Si $b^2 = \bar 1$ avec $b \in \mathbb{Z}/1187\mathbb{Z}$, alors
  $(b-\bar 1)(b+\bar 1) = b^2 - \bar 1 = \bar 0$.  Comme
  $\mathbb{Z}/1187\mathbb{Z}$ est un corps (et en particulier, un
  anneau intègre), un produit ne peut être nul que si un des deux
  facteurs est nul, donc soit $b - \bar 1 = \bar 0$, soit $b + \bar 1
  = \bar 0$, c'est-à-dire soit $b = \bar 1$ soit $b = -\bar 1$.

(B) On a $1\,186 = 2\times 593$.  Le théorème d'Euler ou de Fermat
  assure que $a^{1\,186} \equiv 1 \pmod{1\,187}$ pour tout $a$ non
  multiple de $1\,187$, c'est-à-dire $(a^{593})^2 \equiv 1
  \pmod{1\,187}$ : d'après ce qu'on vient de voir, ceci signifie que
  $a^{593}\equiv 1$ ou $a^{593}\equiv -1$.  (Et ces deux cas se
  produisent effectivement, comme le montrent les exemples de $a=1$ et
  $a=-1$.)  Enfin, si $a$ est multiple de $1\,187$, on a évidemment
  $a^{593} \equiv 0^{593} = 0 \pmod{1\,187}$.  Les trois valeurs
  possibles sont donc : $+1, -1, 0$.

(Remarquons que les deux sous-questions ci-dessus n'ont pas utilisé le
  fait que $593$ était premier, et fonctionnaient également en
  remplaçant $1\,187$ par n'importe quel nombre premier $p$ impair et
  $593$ par $(p-1)/2$.)

(C) Tout d'abord, si $a^{593} \not\equiv 0 \pmod{1\,187}$ alors $a$
  n'est pas multiple de $1\,187$, c'est-à-dire qu'il est premier avec
  $1\,187$.  Lorsque c'est le cas, l'ordre multiplicatif de $a$ doit
  diviser $\varphi(1\,187) = 2\times 593$ : les diviseurs de ce nombre
  sont $1$, $2$, $593$ et $1\,186$.  Le seul élément (de n'importe
  quel groupe, noté multiplicativement) dont l'ordre est $1$ est $1$
  (le neutre) ; la première question montre que le seul élément de
  $(\mathbb{Z}/1187\mathbb{Z})^\times$ dont l'ordre est $2$ est $-1$ ;
  si l'ordre de $a$ est $593$ (en particulier, $a$ n'est pas
  primitif), alors $a^{593} \equiv 1 \pmod{1\,187}$.  Enfin, si
  l'ordre de $a$ est $1\,186$, c'est-à-dire si $a$ est primitif, alors
  $a^{593}$ ne peut pas valoir $1$, et doit donc valoir $-1$.  Tout
  ceci mis ensemble, on a bien : $a^{593} \equiv -1 \pmod{1\,187}$ si
  et seulement si $a \equiv -1 \pmod{1\,187}$ ou bien $a$ est primitif
  modulo $1\,187$.
\end{corrige}

%
%
%
\end{document}