summaryrefslogtreecommitdiffstats
path: root/controle-20101123.tex
blob: 81571674ca2876ca555a700dc41b06e59f2af291 (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
%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
\documentclass[12pt]{article}
\usepackage[francais]{babel}
\usepackage[latin1]{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}}
%
\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{23 novembre 2010}
\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 : 1h30

\newpage

%
%
%

\exercice

(A) Quel entier entre $1500$ et $2500$ est congru à $36$ modulo $47$
et à $49$ modulo $53$ ?

(B) Quel est le plus petit entier naturel multiple de $9$ et de $11$
et congru à $6$ modulo $10$ ?

(C) Quels sont les entier entre $0$ et $100$ congrus à $6$ modulo $18$
et à $15$ modulo $27$ ?

(D) Quels sont les entier entre $0$ et $9000$ congrus à $18$
modulo $91$ et à $24$ modulo $105$ ?

%
%
%

\exercice

On a $561 = 3\times 11\times 17$.

(1) Montrer que $n^{561} \equiv n \pmod{3}$ pour tout entier $n$, et
de même $\mathop{\mathrm{mod}} 11$ et $\mathop{\mathrm{mod}} 17$.
(Indication : la réponse à cette question doit faire intervenir le
nombre $560$ et \emph{non pas} la factorisation de $561$ donnée
ci-dessus.)

(2) En déduire que $n^{561} \equiv n \pmod{561}$ pour tout entier $n$.

%
%
%

\exercice

On admet que le polynôme suivant dans $\mathbb{F}_2[t]$ est
irréductible : $f := t^8 + t^4 + t^3 + t^2 + 1$.

(1) Quel est le nombre d'éléments de $\mathbb{F}_2[t]/(f)$ ?  Que
peut-on en dire et comment a-t-on l'habitude de le noter ?

(2) Dans $\mathbb{F}_2[t]/(f)$, calculer les puissances $\bar t^i$ de
l'élément $\bar t$ représenté par $t$, pour $i$ allant de $0$ à $20$
inclus.  (Ici, « calculer » sous-entend qu'on demande comme d'habitude
le représentant standard, c'est-à-dire celui donné par un polynôme de
degré $<\deg f$.)

(3) On a $255 = 3 \times 5 \times 17$.  L'élément $\bar t$ est-il
primitif ?  Si non, quel est son ordre multiplicatif ?  Si oui,
comment qualifie-t-on le polynôme $f$ du fait de cette propriété ?

(4) Donner un élément primitif de $\mathbb{F}_2[t]/(f)$, différent de
$\bar t$ si on a répondu ci-dessus que $\bar t$ était primitif.
Combien y en a-t-il ?

(5) Quels sont les éléments $\bar\imath$ de $\mathbb{Z}/255\mathbb{Z}$
vérifiant $15\bar\imath = \bar0$ ?  Quels sont les éléments de
$\mathbb{F}_2[t]/(f)$ vérifiant $x^{16} = x$ ?  (Cette fois-ci, on ne
demande pas nécessairement de les écrire sous la forme d'un
représentant standard : n'importe quelle autre écriture conviendra.)
Combien y en a-t-il et que peut-on dire de l'ensemble de ces
éléments ?

(6) Trouver un élément $z$ de $\mathbb{F}_2[t]/(f)$ tel que $z^2 =
\bar t$.

%
%
%
\end{document}