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
|
%% 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{27 novembre 2012}
\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 : 2h
\newpage
%
%
%
\exercice
La décomposition en facteurs premiers de $65\,535$ est : $3 \times 5
\times 17 \times 257$.
(1a) Soit $x$ un entier : que vaut $x^{256}$ modulo $p = 257$ ? (On
discutera selon la valeur de $x$ modulo $p$, et on dira clairement
quelles sont toutes les valeurs possibles que peut prendre $x^{256}$
modulo $p$.)
(1b) Même question que (1a) mais cette fois pour $x^{256}$ modulo $p$
avec $p \in \{3,5,17\}$ (on prendra garde que l'exposant est toujours
$256$ dans cette question, ce n'est pas une erreur de l'énoncé).
(2) Montrer que $x^{256} \equiv 1 \pmod{65\,535}$ si $x$ est premier
avec $65\,535$. Que peut-on en déduire sur l'ordre multiplicatif des
éléments de $(\mathbb{Z}/65535\mathbb{Z})^\times$ ?
(3) Que vaut $\varphi(65\,535)$ ?
(4) Comparer le résultat de la question (2) à l'énoncé du théorème
d'Euler modulo $65\,535$.
(5) Montrer que $x^{257} \equiv x \pmod{p}$ pour tout entier $x$ et
pour tout $p \in \{3,5,17, 257\}$.
(6) En déduire que $x^{257} \equiv x \pmod{65\,535}$ pour tout
entier $x$.
(7) Rappeler pourquoi il existe des éléments de
$(\mathbb{Z}/257\mathbb{Z})^\times$ dont l'ordre multiplicatif vaut
exactement $256$.
(8) On suppose que $x$ est un entier premier avec $65\,535$ et que
l'ordre multiplicatif de sa classe modulo $257$ (qui est un élément de
$(\mathbb{Z}/257\mathbb{Z})^\times$) vaut exactement $256$. Montrer
que la classe de $x$ modulo $65\,535$ (qui est cette fois un élément
de $(\mathbb{Z}/65535\mathbb{Z})^\times$) est elle aussi d'ordre
multiplicatif $256$.
(9) En déduire l'ordre multiplicatif maximal possible d'un élément de
$(\mathbb{Z}/65535\mathbb{Z})^\times$.
(10) Sans aucune hypothèse sur l'entier $x$, combien de valeurs
distinctes peut prendre $x^{256}$ modulo $65\,535$ ? (On ne demande
pas de calculer ces valeurs, uniquement de calculer leur nombre,
c'est-à-dire, si on préfère, le cardinal de l'image de $x \mapsto
x^{256}$ sur $\mathbb{Z}/65535\mathbb{Z}$.)
%
%
%
\exercice
Soit $f = t^8 + t^4 + t^3 + t^2 + 1 \in \mathbb{F}_2[t]$. On admet
que ce polynôme est irréductible. On pose $E = \mathbb{F}_2[t]/(f)$.
(1) Combien d'éléments $E$ a-t-il ? Combien d'éléments $E^\times$ (le
groupe des inversibles de $E$) a-t-il ?
On désignera par $\alpha \in E$ (plutôt que $\bar t$) la classe de $t$
modulo $f$.
(2) Que peut-on dire \textit{a priori} de l'ordre multiplicatif
de $\alpha$ ? C'est-à-dire : quelles sont les valeurs \textit{a
priori} possibles ? (Remarque : $255 = 3 \times 5 \times 17$.)
(3) Calculer les valeurs de $\alpha^i$ dans $E$ (c'est-à-dire la
classe de $t^i$ modulo $f$) pour $i \leq 17$.
Pour permettre de vérifier les calculs, on donne le dernier résultat :
$\alpha^{17} = \alpha^7 + \alpha^4 + \alpha^3$. On notera aussi
$\beta$ cet élément $\alpha^{17} \in E$.
(4) Calculer de même les valeurs de $\alpha^i$ les valeurs suivantes
de $i$ : $34$, $51$, $68$ et $85$ (c'est-à-dire les multiples de $17$
jusqu'à $85$ inclus) ; si l'on préfère, ce sont les premières
puissances de $\beta$.
Pour permettre de vérifier les calculs, on donne le dernier résultat :
$\alpha^{85} = \alpha^7 + \alpha^6 + \alpha^4 + \alpha^2 + \alpha$.
(5) Que vaut l'ordre multiplicatif de $\alpha$ ? Quel est l'ordre
multiplicatif de $\beta = \alpha^{17}$ ?
(6) Que vaut $\beta^{16}$ ?
(7) Vérifier que $\beta^4 + \beta + 1 = 0$.
On pose $g = t^4 + t + 1 \in \mathbb{F}_2[t]$, et $K =
\mathbb{F}_2[t]/(g)$.
On appelle $\Phi\colon \mathbb{F}_2[t] \to E$ l'application $P \mapsto
P(\beta)$ qui à un polynôme $P \in \mathbb{F}_2[t]$ associe la valeur
de celui-ci en $\beta$. Par exemple, la question (7) signifie que
$\Phi(g) = 0$.
(8) (a) Expliquer pourquoi $\Phi(h_1 + h_2) = \Phi(h_1) + \Phi(h_2)$
et $\Phi(h_1 h_2) = \Phi(h_1)\, \Phi(h_2)$ pour tous $h_1,h_2 \in
\mathbb{F}_2[t]$. (b) Montrer que $\Phi(h) = \Phi(h')$ si $h \equiv
h' \pmod{g}$.
(9) Déduire de (8b) qu'on peut définir une application $\varphi \colon
K \to E$ qui envoie la classe (modulo $g$) d'un polynôme $h \in
\mathbb{F}_2[t]$ sur $\Phi(h) \in E$. Déduire de (8a) que
$\varphi(u_1 + u_2) = \varphi(u_1) + \varphi(u_2)$ et $\varphi(u_1
u_2) = \varphi(u_1) \, \varphi(u_2)$ pour tous $u_1,u_2 \in K$.
Comment qualifie-t-on $\Phi$ et $\varphi$ ?
On désignera par $\gamma \in K$ (plutôt que $\bar t$) la classe de $t$
modulo $g$. Ainsi, on a $\varphi(\gamma) = \beta$ (puisque $\Phi(t) =
\beta$).
(10) Montrer que le cardinal de l'image de $\varphi$, autrement dit,
le nombre de valeurs distinctes atteintes par $\varphi$, vaut au
moins $16$. (On pourra, par exemple, dire ce que vaut
$\varphi(\gamma^i)$ et compter toutes les valeurs ainsi atteintes,
sans oublier d'ajouter $\varphi(0)$.) En déduire que $\varphi$ est
injective (=deux éléments distincts de $K$ ont toujours des images
distinctes dans $E$), et que le polynôme $g$ est irréductible.
%
%
%
\end{document}
|
