path: root/controle-20101123.tex

%% 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$ ?

\begin{corrige}
Trouvons d'abord une relation de Bézout entre $47$ et $53$, en
vérifiant du même coup qu'ils sont premiers entre eux.  On a les
divisions euclidiennes successives $53 = 1 \times 47 + 6$, puis $47 =
7 \times 6 + 5$, puis $6 = 1 \times 5 + 1$ : ceci montre que le pgcd
est bien $1$, et on peut ensuite écrire $1 = 1\times 6 - 1\times 5 =
8\times 6 - 1\times 47 = 8\times 53 - 9\times 47$, cette dernière
constituant la relation de Bézout recherchée.

Comme $47$ et $53$ sont premiers entre eux, le théorème chinois assure
que se donner une congruence modulo $47$ et une congruence modulo $53$
équivaut à se donner une congruence modulo $47\times 53$ ; comme
$47\times 53$ est certainement $>1000$, ceci suffira à définir un
unique entier entre $1500$ et $2500$ s'il en existe un.  On sait par
ailleurs que l'entier $36\times 8\times 53 - 49\times 9\times 47$
vérifiera les congruences recherchées ; on peut simplifier le calcul
en calculant $36\times 8 = 288 \equiv 6 \pmod{47}$ et $-49\times 9 =
-441 \equiv 36 \pmod{53}$, ce qui donne $6\times 53 + 36\times 47 =
2010$, qui vérifie les conditions demandées.
\end{corrige}

\ifcorrige\medbreak\else\relax\fi

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

\begin{corrige}
D'après le théorème chinois, être congru à $6$ modulo $10$ et $11$,
comme ceux-ci sont premiers entre eux, revient à être congru à $6$
modulo $10 \times 11 = 110$.  Cherchons maintenant une relation de
Bézout entre $110$ et $9$ : on a $110 = 12\times 9 + 2$ et $9 =
4\times 2 + 1$ donc $1 = 1\times 9 - 4\times 2 = 49\times 9 - 4\times
110$.  Le théorème chinois assure qu'être congru à $6$ modulo $110$ et
à $0$ modulo $9$ équivaut à être congru à $6\times 49\times 9 -
0\times 4\times 110$ modulo $990$ ; or $6\times 49 = 294 \equiv 74
\pmod{110}$ donc $6\times 49\times 9 \equiv 74\times 9 = 666
\pmod{990}$.  Ceci démontre que les entiers congrus à $0$ modulo $9$,
à $6$ modulo $11$ et à $6$ modulo $10$ sont ceux congrus à $666$
modulo $990$, dont le plus petit positif est $666$.
\end{corrige}

\ifcorrige\medbreak\else\relax\fi

(C) Quels sont les entier entre $0$ et $100$ congrus à $12$ modulo $15$
et à $2$ modulo $20$ ?

\begin{corrige}
Les nombres $15$ et $20$ ne sont pas premiers entre eux : leur pgcd
vaut $5$ puisque $15 = 3\times 5$ et $20 = 4\times 5$.  Ceci étant,
les congruences $12$ modulo $15$ et $2$ modulo $20$ sont compatibles
modulo $5$ (toutes deux se réduisent sur $2$).  Vérifier ces deux
congruences revient donc simplement à être congru à $12$ modulo $15$
et à $2$ modulo $4$.  Trouvons une relation de Bézout entre $15$
et $4$ : on a $15 = 3\times 4 + 3$ et $4 = 1\times 3 + 1$ donc $1 =
1\times 4 - 1\times 3 = 4\times 4 - 1\times 15$.  Donc être congru à
$12$ modulo $15$, et à $2$ modulo $4$ (ou ce qui revient au même à $2$
modulo $20$) revient à être congru à $12\times 4\times 4 - 2\times
1\times 15 = 162$ modulo $15\times 4 = 60$.  Le seul nombre entre $0$
et $100$ vérifiant cette congruence est $42$.
\end{corrige}

\ifcorrige\medbreak\else\relax\fi

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

\begin{corrige}
Les nombres $91$ et $105$ ne sont pas premiers entre eux : leur pgcd
est $7$ comme on le voit par exemple en appliquant l'algorithme
d'Euclide ($105 = 1\times 91+14$ puis $91 = 6\times 14 + 7$ puis $14 =
2\times 7$).  Or $18$ et $24$ ne sont pas congrus modulo $7$, donc
aucun nombre congru à $18$ modulo $91$ n'est congru à $24$
modulo $105$.
\end{corrige}

%
%
%

\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$.

\begin{corrige}
(1) On sait que $n^2 \equiv 1 \pmod{3}$ pour tout entier $n$ non
  multiple de $3$ (théorème d'Euler ou petit théorème de Fermat).
  Comme $560$ est multiple de $2$, on a \textit{a fortiori} $n^{560}
  \equiv 1 \pmod{3}$.  Ceci permet d'affirmer $n^{561} \equiv n
  \pmod{3}$ lorsque $n$ n'est pas multiple de $3$ ; or la même égalité
  vaut encore pour $n \equiv 0 \pmod{3}$ (c'est simplement $0=0$).  On
  a bien prouvé $n^{561} \equiv n \pmod{3}$ pour tout $n$.

De même : on sait que $n^{10} \equiv 1 \pmod{11}$ pour tout entier $n$
non multiple de $11$.  Comme $560$ est multiple de $10$, on a
\textit{a fortiori} $n^{560} \equiv 1 \pmod{11}$.  Ceci permet
d'affirmer $n^{561} \equiv n \pmod{11}$ pour $n$ non multiple de $11$,
et c'est encore vrai pour $n$ multiple de $11$.

De même : on sait que $n^{16} \equiv 1 \pmod{17}$ pour tout entier $n$
non multiple de $17$.  Comme $560$ est multiple de $16$, on a
\textit{a fortiori} $n^{560} \equiv 1 \pmod{17}$.  Ceci permet
d'affirmer $n^{561} \equiv n \pmod{17}$ pour $n$ non multiple de $17$,
et c'est encore vrai pour $n$ multiple de $17$.

(2) On a montré $n^{561} \equiv n \pmod{3}$ et $n^{561} \equiv n
\pmod{11}$ et $n^{561} \equiv n \pmod{17}$ pour tout entier $n$.
Comme $3,11,17$ sont premiers entre eux deux à deux, le théorème
chinois assure qu'on a alors la congruence $n^{561} \equiv n$
modulo $3\times 11\times 17 = 561$.
\end{corrige}

%
%
%

\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}