path: root/controle-20141125.tex

%% 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{25 novembre 2014}
\maketitle
\pretolerance=10000
\tolerance=8000

\vskip1truein\relax

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

\bigbreak

%
%
%

\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$ ?
\begin{corrige}
On a évidemment $1\,000\,000! \geq 2$, donc $2^2 = 4$ divise
$2^{1\,000\,000!}$.  Autrement dit, $2^{1\,000\,000!}$ est congru
à $0$ modulo $4$.
\end{corrige}

(2) Que vaut $\varphi(25)$ (où $\varphi$ désigne la fonction
indicatrice d'Euler) ?  Que vaut $2^{20}$ modulo $25$ ?
\begin{corrige}
On a $\varphi(25) = \frac{4}{5}\times 25 = 20$.  Puisque $2$ est
premier à $25$, le théorème d'Euler permet d'en déduire que $2^{20}
\equiv 1 \pmod{25}$.
\end{corrige}

(3) Déduire de (2) la valeur de $2^{1\,000\,000!}$ modulo $25$.
\begin{corrige}
Il est évident que $1\,000\,000!$ est multiple de $20$ (puisque $20$
est un des facteurs du produit $1\,000\,000! = 1 \times 2 \times
\cdots \times 1\,000\,000$), disons $1\,000\,000! = 20\, N$ avec $N$
entier.  Alors $2^{1\,000\,000!} = (2^{20})^N \equiv 1^N = 1
\pmod{25}$.
\end{corrige}

(4) En utilisant le théorème chinois, déduire de (1) et (3) la valeur
de $2^{1\,000\,000!}$ modulo $100$.
\begin{corrige}
D'après les questions (1) et (3), $2^{1\,000\,000!}$ est congru à $0$
modulo $4$ et à $1$ modulo $25$.  On cherche donc quel nombre entre
$0$ et $99$ est congru à $0$ modulo $4$ et à $1$ modulo $25$.

On calcule une relation de Bézout entre $25$ et $4$ : comme $25 =
6\times 4 + 1$, on a $1 = 25 - 6\times 4$.  La version explicite du
thèorème chinois (ou la simple observation de cette formule) montre
alors que $-6\times 4$ est congru à $1$ modulo $25$ et à $0$
modulo $4$.  Autrement dit, $2^{1\,000\,000!} \equiv -6\times 4 = -24
\equiv 76 \pmod{100}$.
\end{corrige}

(5) Quels sont les deux derniers chiffres de l'écriture décimale
de $2^{1\,000\,000!}$ ?
\begin{corrige}
On vient de voir que $2^{1\,000\,000!} \equiv 76 \pmod{100}$,
c'est-à-dire que $2^{1\,000\,000!}$ s'écrit comme $76$ plus un
multiple de $100$, ce dernier ayant ses deux derniers chiffres nuls en
écriture décimale, dont les deux derniers chiffres de
$2^{1\,000\,000!}$ en décimal sont : $76$.
\end{corrige}

%
%
%

\exercice

(1) Vérifier que le polynôme $t^2 + 1 \in \mathbb{F}_7[t]$ est
irréductible.
\begin{corrige}
On vérifie simplement que $0^2 + 1 = 1$, $(\pm 1)^2 + 1 = 2$, $(\pm
2)^2 + 1 = 5$ et $(\pm 3)^2 + 1 = 10 = 3$ dans $\mathbb{F}_7$, donc
$x^2 + 1$ ne s'annule pour aucun $x \in \mathbb{F}_7$, donc $t^2 + 1$
n'a pas de racine dans $\mathbb{F}_7$.  Comme ce polynôme est de
degré $\leq 3$, il est irréductible.

Autre méthode : on peut appliquer le critère d'irréductibilité de
Rabin.  Il s'agit alors de vérifier que $t^2 + 1$ divise $t^{49} - t$
et est premier avec $t^7 - t$.  Pour cela, on calcule modulo $t^2 +
1$ : on a $(\bar t)^2 = -1$ donc $(\bar t)^3 = -\bar t$ et $(\bar t)^4
= 1$, donc $(\bar t)^7 = -\bar t$, donc $(\bar t)^{49} = ((\bar
t)^7)^7 = (-\bar t)^7 = \bar t$.  Ces calculs montrent que $(\bar
t)^{49} - \bar t = 0 \in \mathbb{F}_7[t]/(t^2 + 1)$ et que $(\bar t)^7
- \bar t = -2\bar t \in \mathbb{F}_7[t]/(t^2 + 1)$ : le premier
signifie bien que $t^2 + 1$ divise $t^{49} - t$, et le second signifie
que le reste de la division euclidienne de $t^7 - t$ par $t^2 + 1$
vaut $-2t$ (ou $5t$, si on préfère) ; pour conclure l'algorithme
d'Euclide entre $t^7 - t$ et $t^2 + 1$, il s'agit ensuite de diviser
$t^2 + 1$ par $5t$, ce qui donne $t^2 + 1 = 5t\times 3t + 1$, si bien
que le reste ($1$) est une constante, et le pgcd vaut $1$ donc les
polynomes $t^7 - t$ et $t^2 + 1$ sont bien premiers entre eux, et le
critère de Rabin permet bien d'affirmer que $t^2 + 1 \in
\mathbb{F}_7[t]$ est irréductible.
\end{corrige}

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

(2) Que peut-on dire de $F$ (nombre d'éléments, structure
algébrique) ?
\begin{corrige}
Comme $\deg(t^2+1) = 2$, le nombre d'éléments de $F$ est $7^2 = 49$.
Comme $t^2 + 1$ est irréductible (on vient de le voir), $F$ est un
corps.  C'est donc le corps $\mathbb{F}_{49}$ à $49$ éléments.
\end{corrige}

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$ ?
\begin{corrige}
On a $\alpha^2 = -1$ puisque $\alpha^2 + 1 = 0$ par définition (on
travaille modulo $t^2 + 1$).  Par conséquent, $\alpha^3 = -\alpha$ et
$\alpha^4 = -\alpha^2 = 1$.  [Si on a résolu la question (1) en
  utilisant le critère de Rabin, on a déjà fait ces calculs ci-dessus,
  il n'est bien sûr pas nécessaire de les répéter.]  On peut donc
conclure que $\alpha$ est d'ordre multiplicatif $4$, et comme
$\#(F^\times) = 49 - 1 = 48$, cet élément n'est pas primtif.
\end{corrige}

(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.)
\begin{corrige}
On calcule successivement (et en se rappelant que $\alpha^2 = -1$,
comme expliqué ci-dessus) :
\begin{itemize}
\item[$\bullet$] $(2+\alpha)^2 = 4 + 4\alpha + \alpha^2 = 3+4\alpha$
\item[$\bullet$] $(2+\alpha)^3 = (3+4\alpha)(2+\alpha) = 6 + 11\alpha
  + 4\alpha^2 = 2 + 4\alpha$
\item[$\bullet$] $(2+\alpha)^4 = (3+4\alpha)^2 = 9 + 24\alpha +
  16\alpha^2 = 3\alpha$
\item[$\bullet$] $(2+\alpha)^6 = (2+4\alpha)^2 = 4 + 16\alpha +
  16\alpha^2 = 2 + 2\alpha$
\item[$\bullet$] $(2+\alpha)^8 = (3\alpha)^2 = 9\alpha^2 = 5$
\item[$\bullet$] $(2+\alpha)^{12} = 5\times 3\alpha = \alpha$
\item[$\bullet$] $(2+\alpha)^{16} = 5^2 = 25 = 4$
\item[$\bullet$] $(2+\alpha)^{24} = \alpha^2 = -1$
\item[$\bullet$] $(2+\alpha)^{48} = (-1)^2 = 1$
\end{itemize}
On devait nécessairement trouver $(2+\alpha)^{48} = 1$, puisque
l'ordre multiplicatif de $2+\alpha$ doit diviser l'ordre du
groupe $F^\times$, soit $48$.
\end{corrige}

(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$ ?
\begin{corrige}
L'ordre multiplicatif de $2+\alpha$ doit diviser l'ordre du
groupe $F^\times$, soit $48$.  Comme on a testé tous les diviseurs de
$48$ (à savoir $1, 2, 3, 4, 6, 8, 12, 16, 24, 48$), et que le plus
petit pour lequel $(2+\alpha)^n = 1$ est $48$ lui-même, cet ordre
multiplicatif vaut $48$, c'est-à-dire que $2+\alpha$ est primitif
dans $F$.
\end{corrige}

%
%
%

\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$ ?
\begin{corrige}
Comme $\deg(t^7+t+1) = 7$, le nombre d'éléments de $F$ est $2^7 =
128$.  Comme $t^7 + t + 1$ est irréductible (on l'a admis), $F$ est un
corps.  C'est donc le corps $\mathbb{F}_{128}$ à $128$ éléments.  Le
nombre d'éléments de $F^\times$ est donc $128-1 = 127$.
\end{corrige}

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$ ?
\begin{corrige}
L'ordre multiplicatif de $\gamma$ doit diviser celui du groupe
$F^\times$, c'est-à-dire $127$.  Comme $127$ est premier, ses
diviseurs sont $1$ et $127$, et comme l'ordre de $\gamma$ n'est
pas $1$ (car $\gamma \neq 1$), il ne peut être que $127$.  Autrement
dit, $\gamma$ est primitif dans $F$.
\end{corrige}

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.)
\begin{corrige}
On a $\gamma^7 + \gamma + 1 = 0$ par définition (on travaille
modulo $t^7 + t + 1$), donc $\gamma^7 = -(\gamma + 1) = \gamma + 1$
(on est en caractéristique $2$).  On a donc successivement (et en se
rappelat qu'ici, contrairement à l'exercice précédent, on est en
caractéristique $2$, donc $(u+v)^2 = u^2 + v^2$) :
\begin{itemize}
\item[$\bullet$] $\Frob^0(\gamma) = \gamma$
\item[$\bullet$] $\Frob^1(\gamma) = \gamma^2$
\item[$\bullet$] $\Frob^2(\gamma) = \gamma^4$
\item[$\bullet$] $\Frob^3(\gamma) = \gamma^8 = \gamma\times\gamma^7 =
  \gamma(\gamma+1) = \gamma^2 + \gamma$
\item[$\bullet$] $\Frob^4(\gamma) = (\gamma^2 + \gamma)^2 = \gamma^4 +
  \gamma^2$
\item[$\bullet$] $\Frob^5(\gamma) = (\gamma^4 + \gamma^2)^2 = \gamma^8
  + \gamma^4 = \gamma^4 + \gamma^2 + \gamma$
\item[$\bullet$] $\Frob^6(\gamma) = (\gamma^4 + \gamma^2 + \gamma)^2 =
  \gamma^8 + \gamma^4 + \gamma^2 = \gamma^4 + \gamma$
\item[$\bullet$] $\Frob^7(\gamma) = (\gamma^4 + \gamma)^2 = \gamma^8 +
  \gamma^2 = \gamma$
\end{itemize}
(Ce sont là les conjugués absolus de $\gamma$.)

On devait nécessairement trouver $\Frob^7(\gamma) = \gamma$, puisque
le degré (absolu) de $\gamma$ doit diviser le degré (absolu) de $F$,
c'est-à-dire $7$ (ou, de façon équivalente, $\gamma^{128} = \gamma$ à
cause du petit théorème de Fermat dans les corps finis).
\end{corrige}

%
%
%
\end{document}