diff options
| -rw-r--r-- | controle-20141125.tex | 151 |
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} % % |