summaryrefslogtreecommitdiffstats
path: root/controle-20081202.tex
blob: 98fe596eb4678dab393fafa9992e4d0d56fd3332 (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
%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
\documentclass[12pt]{article}
\usepackage[francais]{babel}
\usepackage[latin1]{inputenc}
\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}}
%
%
%
\begin{document}
\title{INFMDI720\\Contrôle de connaissance\\{\normalsize Rappels mathématiques pour la cryptographie}}
\author{}
\date{2 décembre 2008}
\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.  À
l'intérieur d'un exercice, les questions se suivent normalement dans
un ordre logique, et il est vivement recommandé de les traiter dans
cet ordre.

Le sujet étant volontairement trop long pour le temps imparti, il ne
sera pas nécessaire de traiter tous les exercices pour avoir le
maximum des points.  Il est suggéré de prendre le temps de tous les
lire, pour bien choisir ceux que l'on traitera.

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ée.

L'usage des calculatrices électroniques est interdites.  (Certains
exercices peuvent apparaître calculatoires, mais les calculs sont
toujours faisables à la main en un temps raisonnable, parfois au prix
de quelques astuces.)

Durée : 1h30

\newpage

%
%
%

\exercice

Les deux questions suivantes sont indépendantes.

(1) Montrer que $a^{31} \equiv a \pmod{341}$ pour tout $a \in
\mathbb{Z}$ (note : on a $341 = 11\times 31$).

(2) Pourquoi a-t-on $a^{32} \equiv 1 \pmod{128}$ pour tout $a$ impair
(note : $128 = 2^7$) ?

%
%
%

\exercice

Le calendrier religieux maya (ou Tzolkin) est la combinaison de deux
cycles indépendant, l'un de $13$ jours numérotés de 1 à 13, l'autre de
$20$ jours portant des noms de dieux (dans l'ordre : « Ahau »,
« Imix », « Ik », « Akbal », « Kan », « Chicchan », « Cimi »,
« Manik », « Lamat », « Muluc », « Oc », « Chuen », « Eb », « Ben »,
« Ix », « Men », « Cib », « Caban », « Etznab » et « Caunac »).

Ces deux cycles sont complètement indépendants, c'est-à-dire que si un
jour est numéroté « 11 Ahau », le lendemain sera « 12 Imix », puis
« 13 Ik », puis « 1 Akbal », « 2 Kan » et ainsi de suite jusqu'à
« 4 Caunac » auquel suit « 5 Ahau », etc.  Il n'existe aucune
irrégularité.

(1) Quelle est le nombre de jours d'un cycle du Tzolkin ?  Autrement
dit, au bout de combien de jours après un jour donné retombe-t-on pour
la première fois sur un jour ayant le même numéro et le même nom ?

(2) Sachant que le 2 décembre 2008 est dénommé « 6 Ahau », déterminer
quand aura lieu le prochain jour « 10 Oc » au calendrier religieux
maya.

(3) Les Mayas utilisaient également un calendrier civil (ou Haab) de
$365$ jours exactement\footnote{Ce calendrier était lui-même organisé
  en mois, mais cela ne nous importe pas ici.}, qui se répétait lui
aussi sans irrégularité, et complètement indépendamment du calendrier
religieux Tzolkin.  Quelle est la longueur approximative en années
d'un cycle complet des deux calendriers ?  Autrement dit, combien
d'années faut-il attendre approximativement, à partir d'un jour donné,
pour retrouver pour la première fois un jour ayant la même
dénomination dans les deux calendriers (Tzolkin et Haab) à la fois ?

%
%
%

\exercice

Soit $n = 2^{100}$ et $N = 2^n = 2^{2^{100}}$.

(1) Quel est le reste de la division euclidienne de $n$ par $3$ et par
$5$ ?

% Réponses : 1, 1

(2) Quel est le reste de la division euclidienne de $n$ par $6$,
par $10$ et par $4$ ?

% Réponses : 4, 6, 0

(3) Quel est le reste de la division euclidienne de $N$ par $9$,
par $11$ et par $10$ ?

% Réponses : 7, 9, 6

(4) Quel est le reste de la division euclidienne de $N$ par $99$ ?
Par $990$ ?

% Réponses : 97, 196

%
%
%

\exercice

Une conjecture affirme que pour tout entier $n$ il existe $n' \neq n$
tel que $\varphi(n') = \varphi(n)$ (où $\varphi$ désigne la fonction
indicatrice d'Euler).  On va voir qu'on peut montrer cette conjecture
au moins pour les petites valeurs de $n$.

(1a) Si $n$ est impair, montrer que $\varphi(2n) = \varphi(n)$.

(1b) Si $n$ est pair mais non multiple de $4$, montrer que
$\varphi(\frac{1}{2}n) = \varphi(n)$.

(1c) Si $n$ est multiple de $4$ mais non de $12$, montrer que
$\varphi(\frac{3}{2}n) = \varphi(n)$.

(1d) Si $n$ est multiple de $12$ mais non de $36$, montrer
que $\varphi(\frac{2}{3}n) = \varphi(n)$.

(1e) Si $n$ est multiple de $36$ mais non de $7\times 36 = 252$,
montrer que $\varphi(\frac{7}{6}n) = \varphi(n)$.

(1f) Si $n$ est multiple de $7\times 36 = 252$ mais non de $7^2\times
36 = 1764$, montrer que $\varphi(\frac{6}{7}n) = \varphi(n)$.

(2) En continuant selon la même logique, montrer que la conjecture
énoncée plus haut est valable lorsque $n$ n'est pas multiple de
$(6\times 7 \times 43)^2$.

(3) Si $n$ est multiple de $(6\times 7 \times 43)^2$ mais ni de $27$
ni de $13$, montrer que $\varphi(\frac{13}{18}n) = \varphi(n)$.

(4) Sachant que $(6\times 7 \times 43)^2 \geq 3\times 10^6$, jusqu'à
combien les questions précédentes permettent-elles d'affirmer la
véracité de la conjecture ?

%
%
%

\exercice

Cet exercice décrit le principe l'algorithme de factorisation
« $p-1$ » de Pollard.

\emph{Définition :} On dit qu'un entier naturel $m$ est
     « $B$-friable » (pour $B$ un entier naturel) lorsque tout facteur
     premier $\ell$ de $m$ est $\leq B$.  (Par exemple, $720$ est
     $5$-friable.)

(1) Soit $p$ un nombre premier tel que $p-1$ soit $B$-friable (pour
une certaine borne $B$).  Soient $\ell_1,\ldots,\ell_k$ les nombres
premiers $\leq B$.  Partant de $a \in
(\mathbb{Z}/p\mathbb{Z})^\times$, on effectue les opérations
suivantes : pour $i$ allant de $1$ à $k$, on remplace $a$ par
$a^{\ell_i^{r_i}}$ (ce calcul étant fait dans
$\mathbb{Z}/p\mathbb{Z}$), où $r_i$ est un entier supérieur ou égal à
$\log(p)/\log(\ell_i)$.  Quel est le résultat obtenu (autrement dit,
que vaut $a$ après ces différentes opérations) ?  \emph{Indication :}
montrer qu'on a élevé $a$ à une puissance d'exposant multiple
de $p-1$.

\smallskip

On suppose maintenant que $N$ est un entier non premier à factoriser,
et on espère qu'un de ses facteurs premiers $p$ est tel que $p-1$ soit
$B$-friable avec $B$ assez petit.  (Naturellement, on ne sait pas ce
que vaut $p$ : on cherche justement à le calculer ou, du moins, à
trouver une factorisation non triviale $N = d d'$ avec $d,d'>1$.)

L'algorithme $p-1$ de Pollard effectue le calcul suivant, en partant
d'un nombre $N$ à factoriser et d'une borne $B$ de friabilité
(typiquement de l'ordre de $10^6$) :
\begin{itemize}
\item tirer au hasard un entier $a$ entre $2$ et $N-2$ ;
\item calculer $\pgcd(a,N)$ : s'il est $>1$, terminer : ($*$) on a
  trouvé une factorisation non triviale de $N$ ;
\item énumérer les nombres premiers $\ell_1,\ldots,\ell_k$ inférieurs
  ou égaux à $B$ ;
\item pour $i$ allant de $1$ à $k$ :
\begin{itemize}
\item soit $r \geq \log(N)/\log(\ell_i)$ entier,
\item faire $a \leftarrow a^{\ell_i^r}$ dans $\mathbb{Z}/N\mathbb{Z}$ ;
\end{itemize}
\item calculer $d = \pgcd(a-1,N)$ ;
\item si $1<d<N$, terminer : ($*$) on a trouvé une factorisation non
  triviale de $N$ ;
\item si $d=1$, terminer avec l'erreur suivante : ($\dagger$) il
  n'existe aucun facteur $p$ de $N$ tel que $p-1$ soit $B$-friable (on
  peut essayer d'augmenter $B$ et de recommencer) ;
\item si $d=N$, terminer avec l'erreur suivante : ($\ddagger$) on n'a
  pas eu de chance (on peut recommencer pour un $a$ différent) ou bien
  tous les facteurs $p$ de $N$ sont tels que $p-1$ soit $B$-friable
  (on peut recommancer avec un $B$ plus petit).
\end{itemize}

\smallskip

(2a) Expliquer les affirmations ($*$) « on a trouvé une factorisation
  non triviale » de l'algorithme.

(2b) Expliquer l'affirmation ($\dagger$) « il n'existe aucun facteur
  $p$ de $N$ tel que $p-1$ soit $B$-friable ».  \emph{Indication :}
utiliser la question (1).

(2c) Proposer un exemple de situation pouvant conduire au dernier
cas ($\ddagger$).

%
%
%

\exercice

Soit $p$ un nombre premier congru à $5$ modulo $6$.

(1) Y a-t-il des éléments d'ordre $3$ dans $\mathbb{F}_p^\times$ ?
Quelles sont les solutions de $z^3 = 1$ dans $\mathbb{F}_p$ ?

(2) Montrer que l'application $\mathbb{F}_p \to \mathbb{F}_p$ définie
par $x \mapsto x^3$ est une bijection (c'est-à-dire que chaque valeur
de la cible est atteinte une et une seule fois).

(3) Si $a \in \mathbb{F}_p^\times$, à quoi est isomorphe
$\mathbb{F}_p[t] / (t^3-a)$ ?

%
%
%

\exercice

Montrer que tout $x \in \mathbb{F}_{32}^\times$ est primitif.  Combien
d'éléments de $\mathbb{F}_{64}^\times$ sont primitifs ?

%
%
%

\exercice

Le polynôme $t^2 + 1 \in \mathbb{F}_3[t]$ est-il irréductible ?
Est-il primitif ?

%
%
%
\end{document}