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{Frob}}
%
\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 entiers 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 entiers 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)$ ?  (Il
s'agit comme d'habitude des polynômes modulo $f$.)  Que peut-on en
dire et comment le note-t-on ?

(2a) 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$.)

(2b) Calculer $\bar t^{34} = (\bar t^{17})^2$ et $\bar t^{68} = (\bar
t^{34})^2$ ; puis vérifier que $\bar t^{51} = \bar t^{34} \times \bar
t^{17}$ vaut $\bar t^3 + \bar t$, et que $\bar t^{85} = \bar t^{68}
\times \bar t^{17}$ vaut $\bar t^7 + \bar t^6 + \bar t^4 + \bar t^2 +
\bar t$.

(3) On a $255 = 3 \times 5 \times 17$.  Quel est l'ordre multiplicatif
de l'élément $\bar t$ ?  Est-il primitif ?

(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 é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$.

\begin{corrige}
(1) Le polynôme $f$ étant irréductible, $\mathbb{F}_2[t]/(f)$ est un
  corps.  Son nombre d'éléments est $2^{\deg f} = 2^8 = 256$, et on le
  note donc généralement $\mathbb{F}_{256}$.

(2a) Pour $i < 8$, il n'y a rien de mieux à écrire pour $\bar t^i$ que
  $\bar t^i$.  On peut ensuite calculer successivement (à chaque fois
  on multiplie par $t$ et on soustrait le polynôme $f$ le cas échéant
  pour se ramener à un degré $<8$) :
\begin{itemize}
\item[$\bullet$]$\bar t^8 = \bar t^4 + \bar t^3 + \bar t^2 + 1$
\item[$\bullet$]$\bar t^9 = \bar t^5 + \bar t^4 + \bar t^3 + \bar t$
\item[$\bullet$]$\bar t^{10} = \bar t^6 + \bar t^5 + \bar t^4 + \bar t^2$
\item[$\bullet$]$\bar t^{11} = \bar t^7 + \bar t^6 + \bar t^5 + \bar t^3$
\item[$\bullet$]$\bar t^{12} = \bar t^8 + \bar t^7 + \bar t^6 + \bar
  t^4 = \bar t^7 + \bar t^6 + \bar t^3 + \bar t^2 + 1$
\item[$\bullet$]$\bar t^{13} = \bar t^8 + \bar t^7 + \bar t^4 + \bar
  t^3 + \bar t = \bar t^7 + \bar t^2 + \bar t + 1$
\item[$\bullet$]$\bar t^{14} = \bar t^8 + \bar t^3 + \bar t^2 + \bar
  t = \bar t^4 + \bar t + 1$
\item[$\bullet$]$\bar t^{15} = \bar t^5 + \bar t^2 + \bar t$
\item[$\bullet$]$\bar t^{16} = \bar t^6 + \bar t^3 + \bar t^2$
\item[$\bullet$]$\bar t^{17} = \bar t^7 + \bar t^4 + \bar t^3$
\item[$\bullet$]$\bar t^{18} = \bar t^8 + \bar t^5 + \bar t^4 = \bar
  t^5 + \bar t^3 + \bar t^2 + 1$
\item[$\bullet$]$\bar t^{19} = \bar t^6 + \bar t^4 + \bar t^3 + \bar
  t$
\item[$\bullet$]$\bar t^{20} = \bar t^7 + \bar t^5 + \bar t^4 + \bar
  t^2$
\end{itemize}

(2b) On a calculé $\bar t^{17} = \bar t^7 + \bar t^4 + \bar t^3$, on
en déduit, par application du Frobenius (c'est-à-dire en utilisant le
fait que, dans $\mathbb{F}_{256}$, on a $(u+v)^2 = u^2+v^2$), que
$\bar t^{34} = (\bar t^{17})^2 = \bar t^{14} + \bar t^8 + \bar t^6$ et
en utilisant les valeurs de $\bar t^{14}, \bar t^8$ calculées
ci-dessus, on trouve $\bar t^{34} = \bar t^6 + \bar t^3 + \bar t^2 +
\bar t$.  De même, en appliquant de nouveau le Frobenius, on trouve
$\bar t^{68} = (\bar t^{34})^2 = \bar t^{12} + \bar t^6 + \bar t^4 +
\bar t^2 = \bar t^7 + \bar t^4 + \bar t^3 + 1$.

On a alors $\bar t^{51} = \bar t^{34} \times \bar t^{17} = (\bar t^6 +
\bar t^3 + \bar t^2 + \bar t) \times (\bar t^7 + \bar t^4 + \bar t^3)
= \bar t^{13} + \bar t^8 + \bar t^7 + \bar t^4 = \bar t^3 + \bar t$.

De même, $\bar t^{85} = \bar t^{68} \times \bar t^{17} = (\bar t^7 +
\bar t^4 + \bar t^3 + 1) \times (\bar t^7 + \bar t^4 + \bar t^3) =
\bar t^{14} + \bar t^8 + \bar t^7 + \bar t^6 + \bar t^4 + \bar t^3 =
\bar t^7 + \bar t^6 + \bar t^4 + \bar t^2 + \bar t$.

(3) L'ordre de l'élément $\bar t \in \mathbb{F}_{256}^\times$ doit
diviser l'ordre de ce groupe, c'est-à-dire $255 = 3\times 5 \times
17$.  Il vaut l'un des entiers : $1$, $3$ $5$, $17$,
$3{\times}5{=}15$, $3{\times}17{=}51$, $5{\times}17{=}85$ ou
$3{\times}5{\times}17{=}255$.  Or dans les questions précédentes on a
calculé $\bar t^{15}, \bar t^{51}, \bar t^{85}$ et constaté qu'aucun
d'entre eux ne valait $1$ (et \textit{a fortiori} pas non plus $\bar
t^3$, $\bar t^5$ ou $\bar t^{17}$).  On en déduit que l'ordre de $\bar
t$ ne peut être que $255$, c'est-à-dire que $\bar t$ est primitif.
(On dit donc que le polynôme $f$ est primitif.)

Ceci prouve que le morphisme $\psi\colon \mathbb{Z}/{255}\mathbb{Z}
\to \mathbb{F}_{256}^\times$ (du groupe additif des entiers
modulo $255$ vers le groupe multiplicatif des éléments non nuls du
corps $\mathbb{F}_{256}$) défini par $\bar\imath \mapsto \bar t^i$ est
un isomorphisme.  On va s'en servir dans les questions suivantes.

(4) Les éléments primitifs, c'est-à-dire multiplicativement
générateurs, de $\mathbb{F}_{256}^\times$, correspondent, via
l'isomorphisme $\psi$, aux éléments additivement générateurs de
$\mathbb{Z}/255\mathbb{Z}$, autrement dit les classes modulo $255$ des
entiers premiers à $255$.  Il y en a $\varphi(255) = 2\times 4 \times
16 = 128$, à savoir les $\psi(\bar\imath) = \bar t^i$ avec $i$ non
multiple de $3,5,17$, et on peut donner par exemple $\bar t^2$ ou
encore $\bar t^7$.  (Remarque : pour répondre $\bar t^2$, on pouvait
aussi invoquer l'argument suivant : le Frobenius est un isomorphisme,
donc l'image par lui d'un élément primitif est encore primitif, donc
$\bar t^2, \bar t^4, \bar t^8, \ldots$ sont primitifs.)

(5) Dire que $15 \bar\imath = 0$ dans $\mathbb{Z}/255\mathbb{Z}$
signifie que $15 i$ est multiple de $255 = 15\times 17$, c'est-à-dire
que $i$ est multiple de $17$.  Autrement dit, les (quinze)
$\bar\imath$ qui vérifient ceci sont : $0$, $17$, $34$, $51$, $68$,
$85$, $102$, $119$, $136$, $153$, $170$, $187$, $204$, $221$ et $238$.

Dire que $x^{16} = x$ dans $\mathbb{F}_{256}$ signifie que soit $x=0$
(qui vérifie bien $0^{16}=0$) soit $x^{15} = 1$ (en divisant par $x$).
Dans le second cas, quitte à écrire $x = \psi(\bar\imath)$, dire
$x^{15}=1$ équivaut à $15\bar\imath = \bar 0$ dans
$\mathbb{Z}/255\mathbb{Z}$.  Or on vient de résoudre cette équation.
Les (seize) solutions de $x^{16} = x$ sont donc : $0$, $\bar t^0 = 1$,
$\bar t^{17}$, $\bar t^{34}$, $\bar t^{51}$, $\bar t^{68}$, $\bar
t^{85}$, $\bar t^{102}$, $\bar t^{119}$, $\bar t^{136}$, $\bar
t^{153}$, $\bar t^{170}$, $\bar t^{187}$, $\bar t^{204}$, $\bar
t^{221}$ et $\bar t^{238}$.

L'ensemble $\{x \in \mathbb{F}_{256} : x^{16} = x\}$ forme alors un
corps à $16$ éléments, qui est une copie de $\mathbb{F}_{16}$ dans
$\mathbb{F}_{256}$.

(6) Comme manifestement $0$ ne convient pas, on cherche $z$ tel que
$z^2 = \bar t$ sous la forme $z = \psi(\bar\jmath)$.  L'équation
devient alors $2\bar\jmath = \bar 1$ dans $\mathbb{Z}/255\mathbb{Z}$.
L'inverse de $2$ dans $\mathbb{Z}/255\mathbb{Z}$, si on ne voit pas
immédiatement que c'est $128$, peut se calculer à partir d'une
relation de Bézout entre $2$ et $255$ (soit : $255 = 127\times 2 + 1$
donc c'est $-127 \equiv 128 \pmod{255}$).  L'unique solution de $z^2 =
\bar t$ dans $\mathbb{F}_{256}$ est donc $\bar t^{128}$ (on peut
calculer que c'est $\bar t^7 + \bar t^2 + 1$).

(Autre solution de cette question : on sait qu'appliquer $8$ fois le
Frobenius à n'importe quel élément de $\mathbb{F}_{256}$ retombe sur
l'élément en question, i.e. $\Frob^8(y)=y$ pour tout $y$.  Ici, on
cherche à résoudre $\Frob(z) = \bar t$, et en appliquant $7$ fois le
Frobenius, on voit que cela équivaut à : $\Frob^8(z) = \Frob^7(\bar
t)$, soit $z = \bar t^{128}$.)
\end{corrige}

%
%
%
\end{document}