diff options
| -rw-r--r-- | exercices2.tex | 259 |
1 files changed, 259 insertions, 0 deletions
diff --git a/exercices2.tex b/exercices2.tex new file mode 100644 index 0000000..89f8b69 --- /dev/null +++ b/exercices2.tex @@ -0,0 +1,259 @@ +%% 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{Fr}} +% +\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\\Exercices --- Corrig�\\{\normalsize Rappels math�matiques pour la cryptographie}} +\else +\title{INFMDI720\\Exercices\\{\normalsize Rappels math�matiques pour la cryptographie}} +\fi +\author{} +\date{} +\maketitle +\pretolerance=10000 +\tolerance=8000 + +% +% +% + +\exercice + +D�terminer une relation de B�zout entre les polyn�mes $A = t^7 - t^6 + +t^4 - t + 1$ et $B = t^6 + t^5 - t^4 + t^3 + t^2 + 1$ dans +$\mathbb{F}_3[t]$. Quel est l'inverse de $\bar B$ dans +$\mathbb{F}_3[t]/(A)$�? + +\begin{corrige} +On calcule les divisions euclidiennes successives�: $t^7 - t^6 + t^4 - +t + 1 = (t+1)\penalty0 (t^6+t^5-t^4+t^3+t^2+1) + (t^4+t^3-t^2+t)$, +puis $t^6 + t^5 - t^4 + t^3 + t^2 + 1 = t^2(t^4+t^3-t^2+t) + (t^2+1)$, +puis $t^4 + t^3 - t^2 + t = (t^2+t+1)\penalty0 (t^2+1) - 1$. Le pgcd +de $A$ et $B$ est donc�$1$ (ou $-1$, mais on a choisi de le prendre +unitaire). + +On calcule alors des relations $UP + VQ = D$ comme suit�: + +\begin{itemize} +\item[$\bullet$] $U= -1$�; $P= t^4+t^3-t^2+t$�; $V= t^2+t+1$�; $Q= + t^2+1$�; $D= 1$ (d'apr�s la derni�re division effectu�e). +\item[$\bullet$] $U= -t^2$�; $P= t^4+t^3-t^2+t$�; $V= 1$�; $Q= + t^6+t^5-t^4+t^3+t^2+1$�; $D= t^2+1$ (d'apr�s l'avant-derni�re + division effectu�e). +\item[$\bullet$] $U= -t^2(t^2+t+1)-1 = -t^4-t^3-t^2-1$�; $P= + t^4+t^3-t^2+t$�; $V= t^2+t+1$�; $Q= t^6+t^5-t^4+t^3+t^2+1$�; $D= 1$ + (en rempla�ant la valeur de $t^2+1$ donn�e par la derni�re �galit� � + la place du $Q$ de l'�galit� pr�c�dente). +\item[$\bullet$] $U= 1$�; $P= t^7-t^6+t^4-t+1$�; $V= -(t+1)$�; $Q= + t^6+t^5-t^4+t^3+t^2+1$�; $D= t^4+t^3-t^2+t$ (d'apr�s la premi�re + division effectu�e). +\item[$\bullet$] $U= -t^4-t^3-t^2-1$�; $P= t^7-t^6+t^4-t+1$�; $V= + (t^2+t+1) - (-t^4-t^3-t^2-1)\penalty0 (t+1) = t^5-t^4-t^3-t^2-t-1$�; + $Q= t^6+t^5-t^4+t^3+t^2+1$�; $D= 1$ (en rempla�ant la valeur de + $t^4+t^3-t^2+t$ donn�e par la derni�re �galit� � la place du $P$ de + l'�galit� pr�c�dente. +\end{itemize} + +On a donc trouv� la relation de B�zout�: $(-t^4-t^3-t^2-1) \penalty0 +(t^7-t^6+t^4-t+1) + (t^5-t^4-t^3-t^2-t-1) \penalty0 +(t^6+t^5-t^4+t^3+t^2+1) = 1$. + +Ceci montre que l'inverse de $\bar B = \bar t^6+\bar t^5-\bar t^4+\bar +t^3+\bar t^2+1$ dans $\mathbb{F}_3[t]/(A)$ est $\bar t^5-\bar t^4-\bar +t^3-\bar t^2-\bar t-1$. +\end{corrige} + +% +% +% + +\exercice + +(A)�On admet que le polyn�me $P := t^4 + t^3 + t^2 + t + 1 \in +\mathbb{F}_3[t]$ est irr�ductible. Combien d'�l�ments a $F := +\mathbb{F}_3[t]/(P)$�? + +(B)�Quel est l'ordre (additif) de $\bar t$ dans le groupe additif +de�$F$�? + +(C)�Calculer $\bar t^4$ et $\bar t^5$. Quel est l'ordre +(multiplicatif) de $\bar t$ dans le groupe multiplicatif $F^\times$ +des �l�ments non-nuls de�$F$�? L'�l�ment $\bar t$ est-il primitif�? +Le polyn�me $P$ est-il primitif�? + +(D)�Quels sont les conjugu�s de $\bar t$ (=ses images successives par +le morphisme de Frobenius)�? Quel est le degr� de�$\bar t$�? + +\begin{corrige} +(A)�Le nombre d'�l�ments de $F$ est $3^{\deg P} = 3^4 = 81$ (comme le + nombre de polyn�mes de degr� $<4$ sur�$\mathbb{F}_3$). On peut donc + noter $F = \mathbb{F}_{81}$. Il s'agit d'un corps, puisque $P$ est + irr�ductible. + +(B)�Les multiples additifs de $\bar t$ sont $0$, $\bar t$ et $2\bar t + = -\bar t$, apr�s quoi on retombe sur�$0$ (la caract�ristique de�$F$ + est�$3$). L'ordre additif de $\bar t$, comme celui de n'importe + quel �l�ment non nul dans un corps de caract�ristique�$3$, est + donc�$3$. + +(C)�On a $\bar t^4 = -\bar t^3 - \bar t^2 - \bar t - 1$ comme il + r�sulte d'une division euclidienne (�vidente) de $t^4$ par�$P$. Par + cons�quent, $\bar t^5 = -\bar t^4 - \bar t^3 - \bar t^2 - \bar t = + 1$ (on peut aussi faire la division euclidienne de $t^5$ par�$P$). + Ceci signifie que l'ordre multiplicatif de $\bar t$ divise�$5$, + c'est-�-dire qu'il vaut $1$ ou $5$. Comme il ne vaut pas�$1$ + (puisque $\bar t$ ne vaut pas�$1$), il vaut�$5$. De fait, les + puissances de $\bar t$ sont�: $1$, $\bar t$, $\bar t^2$, $\bar t^3$ + et $-\bar t^3 - \bar t^2 - \bar t - 1$, apr�s quoi on retombe + sur�$1$. Comme $F^\times$ a $80$ �l�ments, $\bar t$ n'est pas + primitif (un �l�ment primitif est un �l�ment d'ordre + multiplicatif�$80$). Ceci signifie pr�cis�ment que le polyn�me $P$ + n'est pas primitif. + +(D)�Le morphisme de Frobenius est l'application $x \mapsto x^3$ + dans�$F$. Les conjugu�s de $\bar t$, c'est-�-dire ses images + successives par le Frobenius sont�: $\bar t$ lui-m�me, $\bar t^3$, + puis $\bar t^9 = \bar t^4 = -\bar t^3 - \bar t^2 - \bar t - 1$ (car + $\bar t^5 = 1$ � ce qu'on a vu), et ensuite on retombe sur $\bar + t^{81} = \bar t$. Le degr� de $\bar t$ est�$4$ (c'est forc�ment le + degr� de�$P$). +\end{corrige} + +% +% +% + +\exercice + +(A)�On admet que le polyn�me $P := t^4 + t + 1 \in \mathbb{F}_2[t]$ +est irr�ductible. Combien d'�l�ments a $F := \mathbb{F}_2[t]/(P)$�? + +(B)�Dresser la liste des puissances successives de $\bar t$ dans�$F$. +Quel est l'ordre de�$\bar t$�? Est-il primitif�? Quel est l'inverse +de�$\bar t$�? Quels sont tous les �l�ments primitifs de�$F$�? Quel +est l'ordre multiplicatif de $\bar t^3$�? M�me question pour $\bar +t^5$. + +(C)�Quels sont les conjugu�s de $\bar t$�? Quel est son degr�? +M�mes questions pour $\bar t^3$. M�mes questions pour $\bar t^5$. + +(D)�Quels sont les �l�ments de l'unique corps � $4$ �l�ments contenu +dans�$F$�? + +\begin{corrige} +(A)�Le nombre d'�l�ments de $F$ est $2^{\deg P} = 2^4 = 16$ (comme le + nombre de polyn�mes de degr� $<4$ sur�$\mathbb{F}_2$). On peut donc + noter $F = \mathbb{F}_{16}$. Il s'agit d'un corps, puisque $P$ est + irr�ductible. + +(B)�On calcule successivement en multipliant par $t$ et en se + rappelant que $t^4 \equiv t+1 \pmod{P}$�: + +\begin{tabular}{r|l} +$i$&$\bar t^i$\\\hline +$0$&$1$\\ +$1$&$\bar t$\\ +$2$&$\bar t^2$\\ +$3$&$\bar t^3$\\ +$4$&$\bar t^4 = \bar t+1$\\ +$5$&$\bar t^2+\bar t$\\ +$6$&$\bar t^3+\bar t^2$\\ +$7$&$\bar t^4 + \bar t^3 = \bar t^3+\bar t+1$\\ +$8$&$\bar t^4+\bar t^2+\bar t = \bar t^2+1$\\ +$9$&$\bar t^3+\bar t$\\ +$10$&$\bar t^4+\bar t^2 = \bar t^2+\bar t+1$\\ +$11$&$\bar t^3+\bar t^2+\bar t$\\ +$12$&$\bar t^4+\bar t^3+\bar t^2 = \bar t^3+\bar t^2+\bar t+1$\\ +$13$&$\bar t^4+\bar t^3+\bar t^2+\bar t = \bar t^3+\bar t^2+1$\\ +$14$&$\bar t^4+\bar t^3+\bar t = \bar t^3+1$\\\hline +$15$&$\bar t^4+\bar t = 1$\\ +\end{tabular} + +L'ordre de $\bar t$ est donc�$15$, il est primitif puisque $\#F^\times += \#F-1 = 15$, tous les �l�ments non-nuls de�$F$ ont �t� list�s +ci-dessus et on a m�me, plus pr�cis�ment, �tabli un isomorphisme de +groupes $(\mathbb{Z}/15\mathbb{Z}) \to F^\times$ par $\bar\imath +\mapsto \bar t^i$. Cet isomorphisme permet de r�pondre facilement aux +questions suivantes�: l'inverse de $\bar t$ est celui qui correspond � +l'oppos� de $1$, soit $\bar t^{14} = \bar t^3+1$. Les �l�ments +primitifs sont ceux qui correspondent aux g�n�rateurs de +$\mathbb{Z}/15\mathbb{Z}$ (c'est-�-dire les classes des nombres +premiers avec $15$, soit $\bar 1$, $\bar 2$, $\bar 4$, $\bar 7$, $\bar +8$, $\bar{11}$, $\bar{13}$, $\bar{14}$), donc $\bar t$, $\bar t^2$, +$\bar t^4 = \bar t+1$, $\bar t^7 = \bar t^3+\bar t+1$, $\bar t^8 = +\bar t^2+1$, $\bar t^{11} = \bar t^3+\bar t^2+\bar t$, $\bar t^{13} = +\bar t^3+\bar t^2+1$ et $\bar t^{14} = \bar t^3+1$. L'ordre +(multiplicatif) de $\bar t^3$ dans�$F^\times$ est le m�me que l'ordre +(additif) de $3$ dans $\mathbb{Z}/15\mathbb{Z}$, soit�$5$, et de m�me +l'ordre multiplicatif de $\bar t^5$ dans�$F^\times$ est�$3$. + +(C)�Le morphisme de Frobenius est l'application $x \mapsto x^2$ +dans�$F$. Les conjugu�s de $\bar t$, c'est-�-dire ses images +successives par le Frobenius sont�: $\bar t$ lui-m�me, $\bar t^2$, +$\bar t^4 = \bar t+1$, $\bar t^8 = \bar t^2+1$ apr�s quoi on retombe +sur $\bar t^{16} = \bar t$. Le degr� de $\bar t$ est�$4$ (c'est +forc�ment le degr� de�$P$). Pour ce qui est du degr� de $\bar t^3$, +ses images successives par le Frobenius sont�: $\bar t^3$ lui-m�me, +$\bar t^6 = \bar t^3+\bar t^2$, $\bar t^{12} = \bar t^3+\bar t^2+\bar +t+1$ et $\bar t^{24} = \bar t^9 = \bar t^3+\bar t$, apr�s quoi on +retombe sur $\bar t^{48} = \bar t^3$�; donc le degr� de $\bar t^3$ est +�galement�$4$. Enfin, pour calculer le degr� de $\bar t^5$, on a ses +images successives qui sont $\bar t^5 = \bar t^2+\bar t$ lui-m�me et +$\bar t^{10} = \bar t^2+\bar t+1$, puis $\bar t^{20} = \bar t^5$, donc +il n'y a que deux conjugu�s (en comptant $\bar t^5$ lui-m�me), et son +degr� est�$2$. + +(D)�On sait que $\mathbb{F}_4$ est contenu dans�$F = \mathbb{F}_{16}$ +car $16$ est une puissance de�$4$, et on sait qu'alors $\mathbb{F}_4 = +\{x\in F : x^4=x\}$. Une fa�on de trouver ces �l�ments est de +r��crire $x^4 = x$ comme $(x^2)^2 = x$ (on retombe sur�$x$ apr�s deux +applications du Frobenius�: ou encore, le degr� de $x$ est $1$ +ou�$2$)�; les �l�ments v�rifiant ceci sont $0$ et $1$, bien s�r, et +aussi $\bar t^5 = \bar t^2+\bar t$ comme on vient de le voir, et +forc�ment $\bar t^5 + 1 = \bar t^2+\bar t+1$ (puisqu'un corps est +stable ar addition). Une autre fa�on de r�soudre $x^4 = x$ est de le +r��crire comme $x=0$ ou bien $x^3 = 1$, c'est-�-dire qu'il s'agit de +$0$ et des �l�ments d'ordre divisant�$3$, donc, d'apr�s l'isomorphisme +d�j� d�termin�, $\bar t^5 = \bar t^2+\bar t$ et $\bar t^{10} = \bar +t^2+\bar t+1$. +\end{corrige} + +% +% +% +\end{document} |