Rewrite the final chapter (on finite fields) to make it lighter.

1 files changed, 166 insertions, 233 deletions

diff --git a/rappels-maths.tex b/rappels-maths.tex
index 7c3312f..dfcad4b 100644
--- a/rappels-maths.tex
+++ b/rappels-maths.tex
@@ -30,7 +30,7 @@
 \newcommand{\ppcm}{\operatorname{ppcm}}
 \newcommand{\signe}{\operatorname{signe}}
 \newcommand{\tee}{\mathbin{\top}}
-\newcommand{\Frob}{\operatorname{Fr}}
+\newcommand{\Frob}{\operatorname{Frob}}
 \renewcommand{\qedsymbol}{\smiley}
 %
 %
@@ -41,7 +41,7 @@
 \maketitle
 {\footnotesize
 \begin{center}
-CVS: \verb=$Id: rappels-maths.tex,v 1.12 2008-11-26 17:35:18 david Exp $=
+CVS: \verb=$Id: rappels-maths.tex,v 1.13 2009-10-21 17:09:11 david Exp $=
 \end{center}
 \par}
 \pretolerance=10000
@@ -717,11 +717,15 @@ a^{\varphi(m)} \equiv 1 \pmod{m}
 Démonstration : l'élément $\bar a \in (\mathbb{Z}/m\mathbb{Z})^\times$
 a un ordre qui doit diviser l'ordre du groupe, i.e. $\varphi(m)$.
 
-Attention ! ne pas confondre l'ordre d'un élément du groupe additif
-$\mathbb{Z}/m\mathbb{Z}$ et l'ordre d'un élément du groupe
-multiplicatif $(\mathbb{Z}/m\mathbb{Z})^\times$.  Exemple : quel est
-l'ordre de $2$ dans $\mathbb{Z}/7\mathbb{Z}$ ? dans
-$(\mathbb{Z}/7\mathbb{Z})^\times$ ?
+\textbf{Attention !} ne pas confondre l'ordre (« additif ») d'un
+élément du groupe additif $\mathbb{Z}/m\mathbb{Z}$ et l'ordre
+(« multiplicatif ») d'un élément du groupe multiplicatif
+$(\mathbb{Z}/m\mathbb{Z})^\times$.  Exemple : quel est l'ordre de $2$
+dans $\mathbb{Z}/7\mathbb{Z}$ ?  (réponse : $7$ car $2+2+2+2+2+2+2 =
+0$ dans $\mathbb{Z}/7\mathbb{Z}$ et qu'on ne trouve pas $0$ avant) ;
+et dans $(\mathbb{Z}/7\mathbb{Z})^\times$ ?  (réponse : $3$ car
+$2\times 2\times 2 = 1$ dans $(\mathbb{Z}/7\mathbb{Z})^\times$ et
+qu'on ne trouve pas $1$ avant).
 
 Cas particulier : « petit théorème de Fermat » : si $p$ est premier,
 alors $a^{p-1} \equiv 1 \pmod{p}$ lorsque $a$ n'est pas multiple
@@ -1026,55 +1030,120 @@ le \textbf{corps de rupture} de $P$ sur $k$.
 
 \subsection{Sous-corps premier et caractéristique}
 
-Caractéristique d'un corps : c'est l'ordre additif de $1$ si celui-ci
-est fini (sinon on convient que c'est $0$).
+Si $\mathbb{F}$ est un corps fini, alors l'ensemble $\{0_{\mathbb{F}},
+1_{\mathbb{F}}, 1_{\mathbb{F}}+1_{\mathbb{F}},
+1_{\mathbb{F}}+1_{\mathbb{F}}+1_{\mathbb{F}}, \ldots\}$ est fini.  Cet
+ensemble a la structure d'un $\mathbb{Z}/p\mathbb{Z}$ avec $p$
+premier : on dit qu'il s'agit du \textbf{(sous-)corps premier}
+de $\mathbb{F}$, et que $p$ en est la \textbf{caractéristique}.
+Autrement dit, ce $p$ est l'ordre additif de l'élément $1$
+de $\mathbb{F}$, et il s'agit toujours d'un nombre premier.
+
+Si $q$ est le cardinal de $\mathbb{F}$, alors $q$ est toujours une
+puissance de $p$ (par exemple, si on sait ce que ça signifie, parce
+que $\mathbb{F}$ est un espace vectoriel de dimension finie $d$ sur
+son corps premier $\mathbb{F}_p$) ; on note typiquement $q = p^d$, et
+alors $d$ s'appelle le \textbf{degré} de $\mathbb{F}$ au-dessus de son
+corps premier $\mathbb{F}_p$.
+
+En particulier, le nombre d'éléments d'un corps fini est toujours une
+puissance $q = p^d$ d'un nombre premier $p$ (il n'y a pas de corps à
+$6$ ou $10$ éléments !), et tout corps fini contient un
+$\mathbb{Z}/p\mathbb{Z}$.
 
-Tout corps de caractéristique $p>0$ contient un
-$\mathbb{Z}/p\mathbb{Z}$, qui en est un sous-corps $\mathbb{F}_p$
-(donc $p$ est premier) : on dit que c'est le sous-corps premier.  Le
-corps est alors un espace vectoriel dessus : le corps est fini, et si
-$d$ est sa dimension, son nombre d'éléments est $p^d$.
+%
+\subsection{Petit théorème de Fermat, unicité des corps finis}
 
-Moralité : le nombre d'éléments d'un corps fini est une puissance $q =
-p^d$ d'un nombre premier $p$ (il n'y a pas de corps à $6$ ou $10$
-éléments !), et le corps contient alors $\mathbb{F}_p =
-\mathbb{Z}/p\mathbb{Z}$ qu'on appelle son corps premier ; et $p$
-s'appelle la caractéristique.
+Dans un corps $\mathbb{F}$ à $q$ éléments, on a $a^{q-1} = 1$ pour
+tout $a \in \mathbb{F}^\times$ (par Lagrange appliqué au groupe
+multiplicatif $\mathbb{F}^\times = \mathbb{F} \setminus\{0\}$ qui
+a $q-1$ éléments).  On a donc $a^q = a$ pour tout $a \in F$ (« petit
+  théorème de Fermat » généralisé aux corps finis).
 
-%
-\subsection{Unicité}
+Ceci peut aussi se dire : le polynôme $t^q - t \in \mathbb{F}[t]$
+s'annule en tout point de $\mathbb{F}$ (tout élément de $\mathbb{F}$
+en est racine).  Comme il est de degré $q$, on a sa factorisation :
+\[
+t^q - t = \prod_{a \in \mathbb{F}} (t-a)
+\]
 
-Dans un corps $F$ à $q$ éléments, on a $a^{q-1} = 1$ pour tout $a \in
-F^\times$ (par Lagrange) donc on a $a^q = a$ pour tout $a \in F$
-(« petit théorème de Fermat » généralisé).
+Cette factorisation étant valable dans n'importe quel corps $L$ (fini
+ou non) contenant $\mathbb{F}$, on voit que $\mathbb{F}$ peut se
+définir (dans n'importe quel corps $L$ le contenant) comme l'ensemble
+des éléments $x$ vérifiant $x^q = x$ (plus explicitement : le petit
+théorème de Fermat signifie que tout élément de $\mathbb{F}$ vérifie
+$x^q = x$, mais réciproquement tout élément de $L$ vérifiant cette
+équation est automatiquement dans $\mathbb{F}$).
 
-Comme le polynôme $t^q-t$, de degré $q$, ne peut avoir que $q$
-racines, si $F$ est contenu dans un corps $L$ plus gros, alors $F =
-\{x\in L : x^q = x\}$.  Moralité : un corps ne peut contenir qu'un
-seul corps fini à $q$ éléments (pour $q$ fixé).
+Ceci constitue une forme d'unicité des corps finis : un corps $L$
+donné ne peut contenir qu'\emph{au plus un} sous-corps $\mathbb{F}$
+ayant $q$ éléments (pour n'importe quel $q$) --- dès qu'il en contient
+un, ce corps est complètement déterminé (comme l'ensemble des éléments
+vérifiant $x^q = x$).
 
-En particulier, le sous-corps premier $\mathbb{F}_p$ d'un corps $L$ de
-caractéristique $p$ est $\mathbb{F}_p = \{x\in L : x^p = x\}$.
+En particulier, le sous-corps premier $\mathbb{F}_p$ d'un corps fini
+$L$ de caractéristique $p$ est $\mathbb{F}_p = \{x\in L : x^p = x\}$.
 
 On admet également l'unicité à isomorphisme près : deux corps finis à
-$q$ éléments, pour le même $q$, sont isomorphes.
+$q$ éléments, pour le même $q$, sont isomorphes.  (C'est-à-dire qu'il
+s'agit abstraitement du même objet, mais dont les éléments peuvent
+être « nommés » différemment.)
 
 %
-\subsection{Morphisme de Frobenius}
-
-Si $K$ est un corps de caractéristique $p$ alors $\Frob\colon K\to K,
-x\mapsto x^p$ (le morphisme de Frobenius) est un morphisme de corps
-($\Frob(xy) = \Frob(x)\,\Frob(y)$ toujours vrai, et $\Frob(x+y) =
-\Frob(x) + \Frob(y)$ car on est en caractéristique $p$ donc tous les
+\subsection{Morphisme de Frobenius, conjugués d'un élément}
+
+Si $\mathbb{F}$ est un corps fini de caractéristique $p$ alors
+l'application $\Frob\colon \mathbb{F}\to \mathbb{F}, x\mapsto x^p$
+(parfois notée $\Frob_p$ pour plus de clarté) est appelée
+\textbf{(morphisme de) Frobenius} de $\mathbb{F}$ (au-dessus
+de $\mathbb{F}_p$).  C'est un morphisme de corps : il vérifie
+$\Frob(x+y) = \Frob(x) + \Frob(y)$ et $\Frob(xy) = \Frob(x)\,\Frob(y)$
+(le second est évident, et le premier est est vrai car on est en
+caractéristique $p$ donc, quand on développe $(x+y)^p$, tous les
 coefficients binomiaux intermédiaires sont multiples de $p$ donc
-nuls).  On le note aussi $\Frob_p$ pour éviter l'ambiguïté.
+nuls).  C'est aussi une bijection de $\mathbb{F}$ sur lui-même
+(c'est-à-dire que $\Frob$ permute les éléments de $\mathbb{F}$, chacun
+ayant un unique antécédent ou racine $p$-ième).
+
+En appliquant plusieurs fois successivement le morphisme $\Frob$ à un
+élément $x \in \mathbb{F}$ où $\mathbb{F}$ est un corps fini à $q =
+p^d$ éléments, on obtient successivement : $x =
+\Frob^0(x)\;,\penalty0\;\; \Frob^1(x) = x^p\;,\penalty0\;\; \Frob^2(x)
+= (x^p)^p = x^{p^2}\;,\penalty0\;\; \Frob^3(x) = (x^{p^2})^p =
+x^{p^3}\;,...\penalty0\;\; \Frob^i(x) = x^{p^i}$.  Ces éléments
+$x^{p^i}$ s'appellent les \textbf{conjugués} de $x$ (au-dessus
+de $\mathbb{F}_p$).
+
+On a vu plus haut que $x^{p^d} = x$ (c'est le petit théorème de
+Fermat), autrement dit, au bout de $d$ applications du Frobenius on
+retombe sur l'élément $x$ de départ ; il se peut qu'on retombe sur $d$
+plus tôt : le plus petit $r$ tel que $x^{p^r} = x$, qui est aussi le
+nombre de conjugués distincts de $x$, s'appelle le \textbf{degré}
+de $x$ (au-dessus de $\mathbb{F}_p$), et ce degré $r$ divise $d$
+(qu'on a appelé le degré de $\mathbb{F}$).  Tous les conjugués de $x$
+ont bien sûr le même degré que $x$.
+
+\bigbreak
 
-Si $q = p^d$, on a souvent besoin d'introduire $\Frob^d = \Frob_q
-\colon x \mapsto x^q$ (composée $d$-ième du Frobenius).  Notamment,
-dans un corps à $q = p^d$ éléments, puisque $x^q = x$ pour tout $x$,
-la composée $d$ fois de $\Frob_p$, soit $\Frob_q$, est l'identité.
-(Pour cette raison, on dit aussi que $\Frob_q$ est le Frobenius
-\emph{au-dessus} de $\mathbb{F}_q$.)
+\textbf{Attention !} si $\mathbb{F}$ est un corps fini à $q = p^d$
+éléments, ne pas confondre les trois choses suivantes :
+\begin{itemize}
+\item L'ordre additif d'un élément $x$ dans $\mathbb{F}$ (groupe
+  additif) : cet ordre vaut toujours $q$ sauf pour $x=0$ (auquel cas
+  c'est $1$).
+\item L'ordre multiplicatif d'un élément $x \neq 0$ dans
+  $\mathbb{F}^\times$ (groupe multiplicatif des éléments non nuls) :
+  cet ordre divise $q-1$ puisque le groupe $\mathbb{F}^\times$ est
+  d'ordre $q-1$.
+\item Le degré $r$ d'un élément $x$ au-dessus de $\mathbb{F}_p$ qu'on
+  vient de définir : ce degré divise $d$.
+\end{itemize}
+Il y a cependant des rapports : par exemple, si $x \neq 0$ est de
+degré $r$ alors son ordre multiplicatif divise $p^r - 1$ (car on a
+$x^{p^r} = x$ par définition de $r$, donc $x^{p^r - 1} = 1$) ;
+notamment, si $x$ est d'ordre $q - 1 = p^d - 1$ (on va voir qu'il
+existe de tels éléments) alors $x$ est de degré $d$ (mais la
+réciproque n'est pas vraie).
 
 %
 \subsection{Existence et inclusions des corps finis}
@@ -1085,132 +1154,35 @@ comme $\mathbb{F}_q \cong \mathbb{F}_p[t]/(f)$ pour un certain
 polynôme $f \in \mathbb{F}_p[t]$ irréductible de degré $d$
 (l'affirmation est qu'il en existe !).
 
+\smallbreak
+
 Si $q = p^d$ et $q' = p^{\prime d'}$, alors $\mathbb{F}_q$ est contenu
 dans $\mathbb{F}_{q'}$ (plus proprement : $\mathbb{F}_{q'}$ contient
 un sous-corps ayant $q$ éléments) si et seulement si : (1) $p=p'$ et
-(2) $d|d'$.  Cela équivaut encore à : $q'$ est une puissance de $q$,
-soit $q' = q^e$.  (Exemple : $\mathbb{F}_4$ est contenu dans
-$\mathbb{F}_{16}$ mais pas 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é $e = d'/d$.
-
-On va voir plus loin comment tester l'irréductibilité d'un polynôme
-sur un corps fini, et comment en produire.
+(2) $d|d'$.  Cela équivaut encore à : $q'$ est une puissance de $q$.
+(Exemple : $\mathbb{F}_4$ est contenu dans $\mathbb{F}_{16}$ mais pas
+dans $\mathbb{F}_8$.)
 
 %
-\subsection{Polynôme minimal}
-
-[Dans les quelques sections qui suivent, le cas important est $q = p$
-  premier (lire alors $p^d$ pour $q^e$).  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é (divisant $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 $\Frob_q$).
-\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
-(sur $\mathbb{F}_q$).
-
-%
-\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}$ où $e$ est son degré.  (Cf. théorème des nombres
-premiers.)
-
-\medbreak
+\subsection{Test de Rabin, factorisation de $t^{p^d}-t$}
 
 \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
+\mathbb{F}_p[t]$ de degré $d$, 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$ (en fait, on peut se contenter de tester pour les
-  diviseurs stricts \emph{immédiats}, c'est-à-dire les $e_1 = e/\ell$
-  avec $\ell$ premier).
+\item[(a)] $f$ divise $t^{p^d}-t$, et
+\item[(b)] $f$ est premier avec $t^{p^e}-t$ pour tout diviseur strict
+  $e$ de $d$ (en fait, on peut se contenter de tester pour les
+  diviseurs \emph{immédiats}, c'est-à-dire les $e = d/\ell$ avec
+  $\ell$ premier).
 \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\footnote{Par exemple, dans ce cas, tout simplement élever $e$
-  fois successivement à la puissance $q$.} 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$.)
+(Remarque : la condition (a) s'écrit $t^{p^d}\equiv t \pmod{f}$, et
+pour la vérifier on applique un algorithme d'exponentiation
+rapide\footnote{Par exemple, dans ce cas, tout simplement élever $d$
+  fois successivement à la puissance $q$.} pour calculer $\bar
+t^{p^d}$ dans $\mathbb{F}_p[t]/(f)$.  De même, la condition (b) se
+teste avec l'algorithme d'Euclide en commençant par calculer $t^{q^e}$
+modulo $f$.)
 
 \smallskip
 
@@ -1227,43 +1199,40 @@ 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.)
 
-\bigbreak
+\medbreak
+
+Le nombre de polynômes unitaires irréductibles de degré $d$ dans
+$\mathbb{F}_p[t]$ vaut approximativement $\frac{1}{d} p^d$ (plus
+exactement, c'est $\frac{1}{d} p^d + O(p^{d/2})$ lorsque $d \to
++\infty$).  Ceci signifie que parmi les $p^d$ polynômes unitaires de
+degré $d$ sur $\mathbb{F}_p$, il y en a une proportion d'environ
+$\frac{1}{d}$ qui sont irréductibles.
+
+Ainsi, pour générer un polynôme irréductible, il est raisonnable de
+tirer un polynôme (unitaire) au hasard, et de tester son
+irréductibilité, et de recommencer jusqu'à obtenir un irréductible.
+
+\medbreak
+
+On a vu plus haut que sur le corps $\mathbb{F}_q$ (lorsque $q = p^d$),
+le polynôme $t^q - t$ se factorise en irréductibles comme $t^q - t =
+\prod_{a \in \mathbb{F}_q} (t-a)$.  Il est utile de savoir que sur
+$\mathbb{F}_p$, ce même polynôme se factorise comme le produit de
+\emph{tous} les polynômes unitaires irréductibles dont le degré $r$
+divise $d$ (plus précisément, chaque polynôme unitaire irréductible
+$f$ de degré $r$ sur $\mathbb{F}_p$ devient, quand on le regarde sur
+$\mathbb{F}_q$, le produit des $(t-a)$ pour les $r$ conjugués $a$ d'un
+élément de degré $r$).  Ce fait peut servir à dénombrer de façon
+précise les polynômes unitaires irréductibles de n'importe quel degré
+sur $\mathbb{F}_p$.
+
+\medbreak
 
 \textbf{Note :} Contrairement à la situation dans les entiers, on peut
 effectuer efficacement la factorisation des polynômes sur les corps
 finis.
 
 %
-\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 par ailleurs $f \equiv 1 \pmod{t^2-t}$.)
-
-%
 \subsection{Éléments primitifs}
 
 \textbf{Théorème :} Le groupe multiplicatif d'un corps fini est
@@ -1271,49 +1240,13 @@ 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-1)$.
-
-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(p^d-1)$.
-
-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$ ; on a donc $\mathbb{F}_4 = \{0,
-1, g^5, g^{10}\}$.
-
-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
+multiplicatif $\mathbb{F}^\times$ 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$.
 
-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}.
+Le nombre d'éléments primitifs est bien sûr $\varphi(q-1)$ (puisque,
+une fois qu'on sait que $\mathbb{F}^\times$ est cyclique, comme il est
+d'ordre $q-1$, le nombre d'éléments qui l'engendrent est connu).
 
 %
 %