summaryrefslogtreecommitdiffstats
path: root/controle-20141125.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2014-11-05 15:20:40 (GMT)
committerDavid A. Madore <david+git@madore.org>2014-11-05 15:20:40 (GMT)
commitbd34c20cb279a6679a3bfa5058b9a6109c109d44 (patch)
tree327bfe5d833ed5fcdf9582b9d708938b7903bdae /controle-20141125.tex
parentf8391a43ebb69775620df7570d8639bdc6ed88ae (diff)
downloadinfmdi720-bd34c20cb279a6679a3bfa5058b9a6109c109d44.zip
infmdi720-bd34c20cb279a6679a3bfa5058b9a6109c109d44.tar.gz
infmdi720-bd34c20cb279a6679a3bfa5058b9a6109c109d44.tar.bz2
Write solution of test.HEADmaster
Diffstat (limited to 'controle-20141125.tex')
-rw-r--r--controle-20141125.tex151
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}
%
%