End of course.

1 files changed, 210 insertions, 2 deletions

diff --git a/rappels-maths.tex b/rappels-maths.tex
index 7fad063..16f0802 100644
--- a/rappels-maths.tex
+++ b/rappels-maths.tex
@@ -41,7 +41,7 @@
 \maketitle
 {\footnotesize
 \begin{center}
-CVS: \verb=$Id: rappels-maths.tex,v 1.7 2008-10-19 18:48:48 david Exp $=
+CVS: \verb=$Id: rappels-maths.tex,v 1.8 2008-10-19 22:44:33 david Exp $=
 \end{center}
 \par}
 \pretolerance=10000
@@ -136,7 +136,7 @@ Le nombre $\pi(x)$ de nombres premiers $\leq x$ est équivalent à
 $\frac{x}{\ln x}$ lorsque $x\to +\infty$ (Hadamard \& de la Vallée
 Poussin : « théorème des nombres premiers »).  Moralement : la
 probabilité qu'un nombre de $n$ bits aléatoire soit premier est
-environ $n\,\ln 2$.
+environ $\frac{1}{n\,\ln 2}$.
 
 Beaucoup de questions ouvertes.  Par exemple : Conjecture des nombres
 premiers jumeaux : existe-t-il une infinité de nombres premiers $p$
@@ -1082,6 +1082,214 @@ dans $\mathbb{F}_8$.)  Lorsque c'est le cas, alors $\mathbb{F}_{q'}
 \cong \mathbb{F}_q[t]/(f)$ pour un certain polynôme $f \in
 \mathbb{F}_q[t]$ irréductible de degré $d'/d$.
 
+On va voir plus loin comment tester l'irréductibilité d'un polynôme
+sur un corps fini, et comment en produire.
+
+%
+\subsection{Polynôme minimal}
+
+[Dans les quelques sections qui suivent, le cas important est $q = p$
+  premier.  On peut ignorer le cas plus général.]
+
+Rappel : dans $\mathbb{F}_q[t]/(f)$ (avec $f$ irréductible unitaire
+pour fixer les idées), on a $f(\bar t) = 0$, c'est-à-dire que $\bar t$
+est racine de $f$.  A contrario :
+
+\textbf{Prop :} Soit $x \in \mathbb{F}_{q^e}$, alors $x$ est racine
+d'un unique polynôme irréductible unitaire sur $\mathbb{F}_q$, et
+celui-ci est de degré divisant $e$.
+
+Ce polynôme s'appelle \textbf{polynôme minimal} de $x$
+sur $\mathbb{F}_q$, et son degré ($\leq e$, donc) s'appelle le
+\textbf{degré} de $x$ sur $\mathbb{F}_q$.
+
+Naturellement, dans $\mathbb{F}_q[t]/(f)$, avec $f$ irréductible
+unitaire, le polynôme minimal de $\bar t$ sur $\mathbb{F}_q$ est $f$.
+Lorsque $a \in \mathbb{F}_q$, le polynôme minimal de $a$ est $t-a$, de
+degré $1$ ; réciproquement, un élément de $\mathbb{F}_{q^e}$ est dans
+$\mathbb{F}_q$ si et seulement si son degré est $1$.
+
+Si $x \in \mathbb{F}_{q^e}$ est de degré exactement $e$
+(c'est-à-dire : pas moins), et que $f$ est son polynôme minimal, alors
+$\mathbb{F}_{q}[t]/(f) \cong \mathbb{F}_{q^e}$ (ce qu'on savait
+déjà...) en envoyant $\bar t$ sur $x$, et plus généralement la classe
+de $g \in \mathbb{F}_q[t]$ sur $g(x)$.
+
+Si on ne précise pas, le polynôme minimal s'entend sur le corps
+premier.
+
+Exercice : déterminer dans $\mathbb{F}_4$ vu comme
+$\mathbb{F}_2[t]/(t^2+t+1)$ les polynômes minimaux des différents
+éléments, et les degrés sur $\mathbb{F}_2$.  (Réponse : $0$ et $1$ ont
+polynôme minimal $t$ et $t+1$ respectivement, et tous deux degré $1$ ;
+$\bar t$ a polynôme minimal $t^2+t+1$ et $\bar t+1$ aussi, tous deux
+ont degré $2$.)
+
+%
+\subsection{Éléments conjugués}
+
+[On peut toujours imaginer $q = p$ premier.]
+
+Si $f$ est irréductible unitaire de degré $e$ sur $\mathbb{F}_q$ alors
+dans $\mathbb{F}_q[t]/(f)$ les racines de $\bar t$ sont : $\bar t$,
+$\bar t^q$, $\bar t^{q^2}$, ..., $\bar t^{q^{e-1}}$.  Cette situation
+porte un nom :
+
+On dit que deux éléments $x, x' \in \mathbb{F}_{q^e}$ sont
+\textbf{conjugués} lorsqu'ils vérifient les conditions équivalentes
+suivantes :
+\begin{itemize}
+\item $x$ et $x'$ ont le même polynôme minimal sur $\mathbb{F}_q$,
+\item il existe $i$ (qu'on peut prendre entre $0$ et $e-1$) tel que
+  $x' = x^{q^i}$ (= on passe de l'un à l'autre en appliquant
+  suffisamment de fois le Frobenius).
+\end{itemize}
+Le nombre d'éléments conjugués à $x$ (en comptant $x$ lui-même) est le
+degré de $x$.  On parle d'un ensemble complet de conjugués.
+
+%
+\subsection{Factorisation de $t^{q^e}-t$}
+
+[On peut toujours imaginer $q = p$ premier.]
+
+Dans la décomposition en facteurs irréductibles de $t^{q^e}-t$ dans
+$\mathbb{F}_q$ :
+\begin{itemize}
+\item chaque polynôme irréductible de degré divisant $e$ sur
+$\mathbb{F}_q$ apparaît une et une seule fois,
+\item chaque facteur correspond à un ensemble complet de conjugués (de
+  cardinal égal au degré du facteur) dans $\mathbb{F}_{q^e}$,
+\item le nombre de facteurs de degré exactement $e$ est $\frac{1}{e}$
+  fois le nombre d'éléments appartenant à $\mathbb{F}_{q^e}$ mais à
+  aucun $\mathbb{F}_{q^{e_1}}$ pour $e_1$ divisant strictement $e$.
+\end{itemize}
+
+\smallbreak
+
+Exercice : Expliquer pourquoi $t^{64}-t$ se
+décompose en irréductibles sur $\mathbb{F}_2$ en : $2$ facteurs de
+degré $1$, $1$ de degré $2$, $2$ de degré $3$ et $9$ de degré $6$.
+
+\medbreak
+
+Le nombre de polynômes irréductibles unitaires de degré $e$ dans
+$\mathbb{F}_q[t]$ est approximativement $\frac{1}{e}q^e$ (l'erreur est
+$O(q^{e/2})$).  Autrement dit, la probabilité qu'un polynôme unitaire
+aléatoire dans $\mathbb{F}_q[t]$ soit irréductible est
+environ $\frac{1}{e}$.  (Cf. théorème des nombres premiers.)
+
+\medbreak
+
+\textbf{Test d'irréductibilité de Rabin :} Étant donné $f \in
+\mathbb{F}_q[t]$ de degré $e$, il est irréductible si et seulement si
+les deux conditions suivantes sont vérifiées :
+\begin{itemize}
+\item $f$ divise $t^{q^e}-t$, et
+\item $f$ est premier avec $t^{q^{e_1}}-t$ pour tout diviseur strict
+$e_1$ de $e$.
+\end{itemize}
+(Remarque : le premier s'écrit $t^{q^e}\equiv t \pmod{f}$, et pour le
+vérifier on applique un algorithme d'exponentiation rapide dans
+$\mathbb{F}_q[t]/(f)$.  De même, la seconde condition se teste avec
+l'algorithme d'Euclide en commençant par calculer $t^{q^{e_1}}$
+modulo $f$.)
+
+\smallskip
+
+Exercice : Vérifier que $f = t^4 + t + 1$ est irréductible dans
+$\mathbb{F}_2[t]$.  (On a $t^4 \equiv t+1 \pmod{f}$ donc $t^8 \equiv
+t^2+1$ donc $t^{16} \equiv t^4 + 1 \equiv t$ donc le premier critère
+est vérifié.  Pour le second, $t^4-t \equiv 1 \pmod{f}$ donc
+l'algorithme d'Euclide termine immédiatement et $t^4-t$ et $f$ sont
+bien irréductibles.)  Vérifier que $g = t^4 + t^3 + 1$ est
+irréductible dans $\mathbb{F}_2[t]$.  (On a $t^4 \equiv t^3+1
+\pmod{g}$ donc $t^8 \equiv t^6+1 \equiv t^3+t^2+t$ donc $t^{16} \equiv
+t^6+t^4+t^2 \equiv t$ donc le premier critère est vérifié.  Pour le
+second, $t^4-t \equiv t^3+t+1 \pmod{g}$ puis $g = t^4+t^3+1 \equiv t^2
+\pmod{t^3+t+1}$ et enfin $t^3+t+1 \equiv 1 \pmod{t^2}$ donc $t^4-t$ et
+$g$ sont bien irréductibles.)
+
+%
+\subsection{Récapitulation : comment manipuler les $\mathbb{F}_q$}
+
+Moralité des paragraphes précédents : comment faire des calculs dans
+$\mathbb{F}_q$ avec $q = p^d$ ?
+
+On sait travailler dans $\mathbb{F}_p = \mathbb{Z}/p\mathbb{Z}$
+(travailler dans $\mathbb{Z}$ et faire des divisions euclidiennes
+par $p$).
+
+Trouver un polynôme irréductible unitaire $f$ de degré $d$ dans
+$\mathbb{F}_p[t]$ : pour cela, choisir un polynôme unitaire aléatoire
+de degré $d$ parmi les $p^d$ possibles, utiliser le test de Rabin pour
+tester son irréductibilité, et recommencer jusqu'à obtenir un $f$ qui
+passe le test (en moyenne, on fera environ $d$ essais).
+
+Représenter les éléments de $\mathbb{F}_q \cong \mathbb{F}_p[t]/(f)$
+par des polynômes de degré $<d$ sur $\mathbb{F}_p$.  L'addition se
+fait terme à terme.  Pour la multiplication, faire suivre d'une
+division euclidienne par $f$ dont on ne conserve que le reste.  Pour
+l'inverse, utiliser une relation de Bézout avec $f$ (cf. le calcul des
+inverses dans $\mathbb{Z}/m\mathbb{Z}$).  Pour l'exponentiation,
+utiliser un algorithme d'exponentiation rapide.
+
+Exercice : Vérifier que $f = t^3 + t + 1 \in \mathbb{F}_2[t]$ est
+irréductible, et s'en servir pour dresser les tables d'opération de
+$\mathbb{F}_8$.  (Pour vérifier que $f$ est irréductible : $t^3 \equiv
+t+1 \pmod{f}$ donc $t^4 \equiv t^2+t$ donc $t^8 \equiv t^4+t^2 \equiv
+t$, et il n'y a pas d'autre condition à vérifier.)
+
+%
+\subsection{Éléments primitifs}
+
+\textbf{Théorème :} Le groupe multiplicatif d'un corps fini est
+cyclique.
+
+Autrement dit, si $\mathbb{F}$ est un corps fini, il existe des
+éléments $g$, dits \textbf{primitifs}, qui engendrent le groupe
+multiplicatif des éléments non nuls de $\mathbb{F}$, c'est-à-dire tels
+que tout élément non nul de $\mathbb{F}$ soit une puissance de $g$.
+
+Le nombre d'éléments primitifs est bien sûr $\varphi(q)$.
+
+Si un élément $g \in \mathbb{F}_q$, avec $q = p^d$, est primitif,
+alors tous ses conjugués sur le corps premier $g^p, g^{p^2}, g^{p^3},
+\ldots, g^{p^{d-1}}$ le sont aussi.  On peut donc aussi dire que leur
+polynôme minimal (commun) est primitif ; il est nécessairement de
+degré $d$.  Le nombre de polynômes irréductibles primitifs de
+degré $d$ sur $\mathbb{F}_p$ est donc $\frac{1}{d} \varphi(d)$.
+
+Exemple : si $g \in \mathbb{F}_{16}^\times$ est primitif, alors
+$\{g,g^2,g^4,g^8\}$ est un ensemble complet de conjugués
+(sur $\mathbb{F}_2$), tous primitifs ; $\{g^7,g^{14},g^{13},g^{11}\}$
+est également un ensemble complet de conjugués, également primitifs
+car $7$ engendre $\mathbb{Z}/15\mathbb{Z}$ ; $\{g^3,g^6,g^{12},g^9\}$
+en est un autre, de degré $4$ mais \emph{non primitifs} ; enfin,
+$\{g^5,g^{10}\}$ est un ensemble complet de conjugués de degré $2$ ;
+et $\{1=g^{15}\}$ et $\{0\}$ sont les deux seuls éléments de degré $1$
+sur le corps de base $\mathbb{F}_2$.
+
+Exercice : on a trouvé précédemment deux polynômes irréductibles
+unitaires $f = t^4 + t + 1$ et $g = t^4 + t^3 + 1$ de degré $4$
+sur $\mathbb{F}_2$.  Sont-ils primitifs ?  (Réponse : oui.)  En
+admettant que $h = t^4 + t^3 + t^2 + t + 1$ est irréductible, est-il
+primitif ?  (Réponse : non, car $t^5 \equiv 1 \pmod{h}$.)
+
+\smallskip
+
+Moralité : Donné un élément $g \in \mathbb{F}_q^\times$ primitif, avec
+$q = p^d$, ou bien son polynôme minimal $\pi \in \mathbb{F}_p[t]$
+(voir $g$ comme $\bar t \in \mathbb{F}_p[t]/(\pi)$), on peut
+représenter les éléments de $\mathbb{F}_q$ de deux façons : soit comme
+des polynômes de degré $<d$ en $g$ (en $\bar t$), soit comme zéro et
+des puissances entre $0$ et $q-1$ de $g$ (de $\bar t$).  Dans le
+premier cas, l'addition est facile et la multiplication est un peu
+plus difficile, dans le second cas, la multiplication est facile et
+l'addition presque impossible.  Passer de la seconde représentation à
+la première est facile ; le passage dans le sens inverse (par exemple,
+écrire $1+g$ comme une puissance de $g$) correspond au problème du
+\emph{logarithme discret}.
+
 %
 %
 %