Write solution of test.HEADmaster

1 files changed, 148 insertions, 3 deletions

diff --git a/controle-20141125.tex b/controle-20141125.tex
index 940e0f6..f326aac 100644
--- a/controle-20141125.tex
+++ b/controle-20141125.tex
@@ -44,14 +44,14 @@
 \title{INFMDI720\\Contrôle de connaissance\\{\normalsize Rappels mathématiques pour la cryptographie}}
 \fi
 \author{}
-\date{26 novembre 2013}
+\date{25 novembre 2014}
 \maketitle
 \pretolerance=10000
 \tolerance=8000
 
 \vskip1truein\relax
 
-\textbf{Consignes :}
+\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
@@ -66,7 +66,7 @@ L'usage des calculatrices électroniques est interdit.
 
 Durée : 2h
 
-\newpage
+\bigbreak
 
 %
 %
@@ -82,17 +82,53 @@ $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}
 
 %
 %
@@ -102,11 +138,41 @@ de $2^{1\,000\,000!}$ ?
 
 (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
@@ -114,6 +180,15 @@ $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$.)
@@ -124,10 +199,39 @@ $(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}
 
 %
 %
@@ -142,6 +246,12 @@ 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
@@ -151,6 +261,13 @@ $t$ modulo $t^7 + t + 1$).
 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$.
@@ -161,6 +278,34 @@ $\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}
 
 %
 %