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
|
%% 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 :}
Ce sujet comporte un unique exercice. Les questions dépendent les
unes des autres, mais ont été formulées de manière que le fait de ne
pas savoir répondre à l'une d'entre elles, si on en admet le résultat,
ne soit normalement pas handicapant pour la suite. Il est cependant
recommandé de les traiter dans l'ordre où elles sont écrites.
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 : 1h30
\newpage
%
%
%
\renewcommand*{\thefootnote}{(\alph{footnote})}
\bigbreak\noindent\textbf{Exercice~unique.}
(1) Quel est l'ordre multiplicatif de $2$ dans
$\mathbb{F}_{11}^\times$ ? Comment peut-on le qualifier ?
(2) Expliquer pourquoi $\bar\imath \mapsto 2^i$ définit un
isomorphisme de groupes de $\mathbb{Z}/10\mathbb{Z}$ (additif) sur
$\mathbb{F}_{11}^\times$ (multiplicatif).
(3) Montrer qu'il n'existe aucun $x \in \mathbb{F}_{11}$ tel que $x^2
= 2$ (dans $\mathbb{F}_{11}$).
(4) Montrer que le polynôme $t^2 - 2$ est irréductible dans
$\mathbb{F}_{11}[t]$.
On note $K = \mathbb{F}_{11}[t] / (t^2 - 2)$ l'anneau quotient de
$\mathbb{F}_{11}[t]$ par le polynôme $t^2-2$.
(5) Combien $K$ a-t-il d'éléments ? Que peut-on déduire de (4) sur
l'anneau $K$ ?
Dans ce qui suit, on notera\footnote{Comme on ne parlera jamais de
nombres réels, et notamment pas du nombre réel noté de la même
manière, ceci ne devrait pas causer de confusion.} « $\sqrt{2}$ »
(plutôt que $\bar t$) la classe de l'indéterminée $t$ dans $K$.
(6) Expliquer brièvement pourquoi cette notation est raisonnable.
Expliquer brièvement pourquoi tous les éléments de $K$ s'écrivent sous
la forme $a + b\sqrt{2}$ avec $a,b \in \mathbb{F}_{11}$ uniquement
déterminés.
(7) Quel est l'ordre multiplicatif de $\sqrt{2}$ dans $K^\times$ ?
(8) On note $\Frob\colon K \to K$ l'application $x \mapsto x^{11}$.
Rappeler brièvement ce qu'on peut dire sur $\Frob$.
(9) Que vaut $\Frob(a)$ si $a \in \mathbb{F}_{11}$ ? Que vaut
$\Frob(\sqrt{2})$ ? Que vaut $\Frob(a+b\sqrt{2})$ lorsque $a,b \in
\mathbb{F}_{11}$ ? (On demande évidemment une réponse meilleure que
$(a+b\sqrt{2})^{11}$...)
(10) Rappeler brièvement pourquoi il existe un isomorphisme de groupes
de $\mathbb{Z}/120\mathbb{Z}$ (additif) sur $K^\times$
(multiplicatif). (On ne demande pas de l'expliciter.)
(11) Calculer l'inverse de $13$ dans l'anneau
$\mathbb{Z}/120\mathbb{Z}$. (On le représentera par un entier entre
$0$ et $119$.)
(12) Déduire de (10) et (11) que pour tout $x \in K$ il existe un
unique $y \in K$ tel que $x = y^{13}$ (on pourra distinguer les deux
cas $x \in K^\times$ et $x=0$). Expliciter $y$ en fonction de $x$.
(13) Calculer $(2+\sqrt{2})^r$ dans $K$ pour $r$ valant $2$ et et $4$,
puis pour $r$ valant $11$ (il est recommandé d'utiliser la
question (9)), $22$ et $33$, et enfin pour $r$ valant $37$.
(14) En utilisant (12) et (13), résoudre l'équation $y^{13} =
2+\sqrt{2}$ dans $K$ (en l'indéterminée $y$).
%
%
%
\end{document}
|
