summaryrefslogtreecommitdiffstats
path: root/controle-20141125.tex
blob: 940e0f6a4f9be3641b91eb9f685270268cb5449b (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
%% 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 :}

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

%
%
%

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

\exercice

On rappelle que $1\,000\,000! = 1 \times 2 \times 3 \times \cdots
\times 1\,000\,000$ (produit de tous les entiers entre $1$ et
$1\,000\,000$).  On s'intéresse au nombre $2^{1\,000\,000!}$.

(1) Pourquoi $4$ divise-t-il $2^{1\,000\,000!}$ ?  À quoi
$2^{1\,000\,000!}$ est-il congru modulo $4$ ?

(2) Que vaut $\varphi(25)$ (où $\varphi$ désigne la fonction
indicatrice d'Euler) ?  Que vaut $2^{20}$ modulo $25$ ?

(3) Déduire de (2) la valeur de $2^{1\,000\,000!}$ modulo $25$.

(4) En utilisant le théorème chinois, déduire de (1) et (3) la valeur
de $2^{1\,000\,000!}$ modulo $100$.

(5) Quels sont les deux derniers chiffres de l'écriture décimale
de $2^{1\,000\,000!}$ ?

%
%
%

\exercice

(1) Vérifier que le polynôme $t^2 + 1 \in \mathbb{F}_7[t]$ est
irréductible.

On pose $F := \mathbb{F}_7[t]/(t^2 + 1)$.

(2) Que peut-on dire de $F$ (nombre d'éléments, structure
algébrique) ?

Dans ce qui suit, on notera $\alpha$, plutôt que $\bar t$, l'élément
de $F$ représenté par l'indéterminée $t$ (autrement dit, la classe de
$t$ modulo $t^2 + 1$).

(3) Quel est l'ordre multiplicatif de $\alpha \in F^\times$ ?
L'élément $\alpha$ est-il primitif dans $F$ ?

(Il pourra être utile, pour simplifier certains calculs, de se
rappeler que l'élément $6 \in \mathbb{F}_7$ s'écrit aussi $-1$.)

(4) Que valent $(2+\alpha)^2$, $(2+\alpha)^3$, $(2+\alpha)^4$,
$(2+\alpha)^6$, $(2+\alpha)^8$, $(2+\alpha)^{12}$, $(2+\alpha)^{16}$,
$(2+\alpha)^{24}$ et $(2+\alpha)^{48}$ ?  (Cette dernière valeur
devrait permettre de vérifier que les calculs ont été correctement
menés : il est donc conseillé de se demander \textit{a priori} quelle
valeur on doit nécessairement trouver.)

(5) En utilisant les valeurs calculées à la question précédente, quel
est l'ordre multiplicatif de $2+\alpha \in F^\times$ ?  L'élément
$2+\alpha$ est-il primitif dans $F$ ?

%
%
%

\exercice

On admettra que le polynôme $t^7 + t + 1 \in \mathbb{F}_2[t]$ est
irréductible.

On pose $F := \mathbb{F}_2[t]/(t^7 + t + 1)$.

(1) Que peut-on dire de $F$ (nombre d'éléments, structure
algébrique) ?  Quel est le nombre d'éléments de $F^\times$ ?

Dans ce qui suit, on notera $\gamma$, plutôt que $\bar t$, l'élément
de $F$ représenté par l'indéterminée $t$ (autrement dit, la classe de
$t$ modulo $t^7 + t + 1$).

(2) \emph{Sans faire aucun calcul}, que peut-on dire de l'ordre
multiplicatif de $\gamma$ dans $F^\times$ ?  En remarquant que
l'entier $127$ est premier, quel est exactement l'ordre multiplicatif
de $\gamma$ dans $F^\times$ ?

On rappelle que $\Frob\colon F\to F$ est l'application $x \mapsto
x^2$.

(3) Calculer $\Frob^i(\gamma)$ (c'est-à-dire $\gamma^{2^i}$) pour $0
\leq i \leq 7$.  (Il peut être utile de commencer par calculer
$\gamma^7$.  Par ailleurs, la valeur $\Frob^7(\gamma)$ devrait
permettre de vérifier que les calculs ont été correctement menés : il
est donc conseillé de se demander \textit{a priori} quelle valeur on
doit nécessairement trouver.)

%
%
%
\end{document}