renommage massif : séparation des fichiers de configuration des chapitres etc.

1 files changed, 1746 insertions, 0 deletions

diff --git a/chapitres/corps-finis.tex b/chapitres/corps-finis.tex
new file mode 100644
index 0000000..bdb9198
--- /dev/null
+++ b/chapitres/corps-finis.tex
@@ -0,0 +1,1746 @@
+\ifx\danslelivre\undefined
+\documentclass[9pt]{smfart-moi}
+\usepackage{stmaryrd}
+\usepackage{wasysym}
+\usepackage{graphics}
+\usepackage[usenames,dvipsnames]{xcolor}
+\input{commun}
+\input{smf}
+\input{adresse}
+%\input{gadgets}
+\input{francais}
+\input{numerotation}
+\input{formules}
+\input{encoredesmacros}
+\usepackage{srcltx}
+
+\title{Corps finis}
+
+\externaldocument{extensions-algebriques}
+\externaldocument{algo-corps-finis}
+\externaldocument{correspondance-galois}
+
+\begin{document}
+\maketitle
+\tableofcontents
+\else
+\chapter{Corps finis}
+\fi
+
+\section{Propriétés élémentaires}
+
+\subsection{Caractéristique}
+
+Soit $k$ un corps.  Le noyau de l'unique morphisme d'anneaux $𝐙→k$ est
+un idéal premier de $𝐙$.  On rappelle que la \emph{caractéristique} de
+$k$ désigne le générateur positif ou nul de cet idéal : on le note
+$\car k$.  C'est un nombre premier (souvent noté $p$) ou bien $0$.
+Lorsque $\car k$ est un nombre premier $p>0$, l'image de $\ZZ\to k$
+est isomorphe à $\ZZ/p\ZZ$.
+
+Pour tout nombre premier $p$, on note $𝐅_p$ le quotient $𝐙/p𝐙$.  C'est
+un corps (car c'est un anneau intègre fini) de caractéristique $p$ à
+$p$ éléments.  Pour tout corps $k$ de caractéristique $p$, l'image de
+$\ZZ \to k$ est un sous-corps de $k$ isomorphe à $\FF_p$, qui est le
+plus petit sous-corps de $k$ (car les sous-corps de $k$ sont eux aussi
+de caractéristique $p$) et que l'on appelle \emph{corps premier}
+de $k$.
+
+On appelle par ailleurs \emph{exposant caractéristique} \index{exposant
+caractéristique} de $k$ l'entier valant $1$ si $\car k= 0$ et valant $\car k$ sinon.
+
+\begin{lemme2}\label{structures-sur-corps-premier}
+Soit $p$ un nombre premier.
+
+Un groupe abélien $M$ peut être munie d'une structure d'espace
+vectoriel sur le corps $\FF_p$ exactement lorsque tout élément $x\in
+M$ vérifie $px = 0$, auquel cas cette structure de $\FF_p$-espace
+vectoriel est unique.
+
+Un anneau $A$ non nécessairement commutatif peut-être muni d'une
+structure de $𝐅_p$-algèbre non nécessairement commutative si et
+seulement si l'image de $p$ dans $A$ par le morphisme canonique (et
+unique) $𝐙→A$ est nulle.  Cette structure est alors unique.
+\end{lemme2}
+\begin{proof}
+Pour ce qui est de la première affirmation, tout $\FF_p$-espace
+vectoriel doit manifestement vérifier $px = 0$ pour tout $x$, et si un
+groupe abélien $M$ vérifie cette condition, on peut alors poser $\bar
+k\cdot x = k x$, pour tous $k \in \ZZ$, dont on note $\bar k \in
+\FF_p$ la classe modulo $p$, et tout $x \in M$, ce qui définit une
+structure de $\FF_p$ espace vectoriel sur $M$, qui était la seule
+possible car $\bar k = k\cdot \bar 1$ dans $\FF_p$.
+
+En particulier, toute $\FF_p$-algèbre non nécessairement
+commutative $A$ doit vérifier $p 1_A = 0$, c'est-à-dire que l'image de
+$p$ par le morphisme $\ZZ \to A$ est nulle ; et si cette condition est
+satisfaite dans un anneau non nécessairement commutatif $A$ alors $p x
+= p 1_A x = 0$ pour tout $x \in A$ donc on vient de voir qu'il y a une
+unique façon de mettre sur $A$ une structure de $\FF_p$-espace
+vectoriel, qui est clairement une structure de $\FF_p$-algèbre non
+nécessairement commutative.
+\end{proof}
+
+\begin{lemme2}\label{anneaux-a-p-elements}
+Soit $A$ un anneau non nécessairement commutatif ayant $p$ éléments,
+où $p$ est un nombre premier.  Alors il existe un unique isomorphisme
+entre $\FF_p$ et $A$.
+\end{lemme2}
+\begin{proof}
+L'image du morphisme d'anneaux $\ZZ \to A$ est un sous-anneau de $A$
+dont le cardinal doit diviser $p$ ; comme $0_A \neq 1_A$ (sans quoi
+$A$ serait l'anneau nul, qui a un seul élément, ce qui n'est pas le
+cas), ce cardinal est $p$, c'est-à-dire que $\ZZ \to A$ est surjectif.
+Il définit donc un isomorphisme $\ZZ/n\ZZ \buildrel\sim\over\to A$
+avec $n$ le générateur positif de son noyau, et en comparant les
+cardinaux on voit que $n=p$, de sorte qu'on a un isomorphisme $\FF_p
+\buildrel\sim\over\to A$, qui était visiblement le seul possible.
+\end{proof}
+
+On peut donc parler \emph{du} corps fini ayant $p$ éléments, et il n'y
+a pas de problème à identifier $\FF_p$ au corps premier de n'importe
+quel corps de caractéristique $p$.
+
+\begin{proposition2}
+Soit $F$ un corps fini.  Alors, la caractéristique de $F$ est un
+nombre premier $p>0$ et le cardinal de $F$ est une puissance de $p$.
+\end{proposition2}
+\begin{démo}[Démonstration de la proposition]
+Le morphisme $𝐙→F$ n'est pas injectif car $F$ est fini donc
+$\car(F)≠0$.  D'autre part, si $p=\car(F)$, le
+lemme \ref{structures-sur-corps-premier} assure que $F$ un
+$\FF_p$-espace vectoriel (de façon unique).  Si $r=\dim_{\FF_p}(F)$
+(nécessairement finie), on a $\# F=p^r$.
+\end{démo}
+
+Il est fréquent, lorsqu'on a affaire à un corps fini, de noter $p$ sa
+caractéristique et $q$ son nombre d'éléments (qui en est donc une
+puissance), à tel point que ces notations sont parfois utilisées, si
+cela ne cause pas de confusion, sans avoir été introduites.  En
+particulier, une expression telle que « soit $F$ un corps fini de
+  cardinal $p^r$ » sous-entendra toujours que $p$ est un nombre
+premier et $r>0$ un entier naturel non nul.
+
+\begin{remarque2}
+On peut montrer que tout corps gauche fini est commutatif (théorème de
+Wedderburn ; nous en donnerons une démonstration en \ref{Wedderburn}),
+ou même que toute algèbre à division alternative mais non
+nécessairement associative est un corps fini.
+\end{remarque2}
+
+\subsection{Le morphisme de Frobenius}
+
+\begin{proposition2}[petit théorème de Fermat]\label{petit-theoreme-fermat}
+Soit $F$ un corps fini ayant $q$ éléments.  Alors tout élément $x$
+de $F$ vérifie $x^q = x$.  Plus précisément, les racines du polynôme
+$X^q-X$ dans $F$ sont tous les éléments de $F$, chacun avec
+multiplicité $1$ : on a
+\[
+X^q - X = \prod_{a \in F} (X-a)
+\]
+\end{proposition2}
+\begin{proof}
+Le groupe multiplicatif $F^×$ des inversibles de $F$ est
+d'ordre $q-1$, donc si $x \neq 0$ on a $x^{q-1} = 1$ donc $x^q = x$ ;
+le cas $x=0$ est trivial.  Pour ce qui est de la seconde affirmation,
+on vient de montrer que $\prod_{a \in F} (X-a)$ divise $X^q-X$, et
+comme ces deux polynômes sont unitaires et de même degré, ils sont
+égaux.
+\end{proof}
+
+\begin{corollaire2}\label{unicite-corps-q-elements-pour-inclusion}
+Si $K$ est un corps de caractéristique $p>0$, alors pour toute
+puissance $q = p^r$ de $p$, il existe au plus un sous-corps de $K$
+ayant $q$ éléments.
+\end{corollaire2}
+\begin{proof}
+Si $F$ est un sous-corps de $K$ à $q$ éléments, alors la
+proposition \ref{petit-theoreme-fermat} montre que $F$ est exactement
+l'ensemble des racines de $X^q-X$ (dans $F$ donc dans $K$), ce qui
+prouve l'unicité.
+\end{proof}
+
+Autrement dit, un corps à $q$ éléments est unique comme sous-corps de
+n'importe quel sur-corps.  On va voir
+en \ref{existence-et-unicite-corps finis} qu'il est également unique à
+isomorphisme près (mais pas à isomorphisme unique près).
+
+\begin{proposition2}\label{morphisme-de-frobenius}
+Soient $p$ un nombre premier et $A$ une $𝐅_p$-algèbre.  L'application
+$\Frob|_A\colon A→A$ donnée par $a↦a^p$ est un \emph{endomorphisme} de $A$.
+\end{proposition2}
+\begin{démo}
+Seule l'identité $\Frob|_A(x+y)=\Frob|_A(x)+\Frob|_A(y)$ n'est pas
+évidente.  Elle résulte de la formule du binôme de Newton et de la
+congruence $\frac{p!}{i!(p-i)!}≡0\pmod{p}$ pour tout $0<i<p$.
+\end{démo}
+
+Ce morphisme est le \emph{Frobenius}\index{Frobenius} de $A$ (ou
+\emph{Frobenius absolu}), souvent noté $\Frob|_A$ (ou parfois
+$\Frob_A$) ou simplement $\Frob$.  Lorsque cela ne semble pas prêter à
+confusion, on notera $A^p⊆A$ son image.
+
+Lorsque $k$ est un corps, $\Frob|_k$ est injectif puisque son noyau
+est nul ; par conséquent, lorsque $F$ est un corps fini, $\Frob|_F$
+est bijectif, et on en déduit que les corps finis sont parfaits
+(\refext{Alg}{corps-parfait}).  En fait, puisque $\Frob^r(x) =
+x^{p^r}$, lorsque $F$ est un corps fini ayant $q = p^r$ éléments, la
+proposition \ref{petit-theoreme-fermat} se traduit par $(\Frob|_F)^r =
+\Id_F$ (on verra plus loin que l'ordre de $\Frob|_F$ est
+exactement $r$).
+
+\begin{lemme2}\label{sous-corps-a-q-elements}
+Soient $p$ un nombre premier et $q=p^r$ une puissance de $p$.  Soit
+$K$ un corps de caractéristique $p$ sur lequel le polynôme $X^q-X$ est
+scindé.  Alors l'ensemble $\Fix(\Frob^r_K)$ des racines du polynômes
+$X^q-X$ dans $K$ est un sous-corps de $K$ à $q$ éléments (dont on a vu
+l'unicité en \ref{unicite-corps-q-elements-pour-inclusion}).
+\end{lemme2}
+\begin{proof}
+L'ensemble des racines de $X^q-X$ est un sous-corps de $K$ puisque
+c'est l'ensemble $\Fix(\Frob^r_K)$ des points fixes du morphisme de
+corps $\Frob^r_K$.  Comme la dérivée du polynôme $X^q-X$ est $-1$, les
+racines de ce polynôme sont toutes simples et il y en a, dans $K$ où
+il est supposé scindé, exactement $q$ : ainsi, $\Fix(\Frob^r_K)$ est
+bien un sous-corps de $K$ à $q$ éléments.
+\end{proof}
+
+\begin{proposition2}\label{existence-et-unicite-corps finis}
+Soit $q=p^r$ une puissance d'un nombre premier.  Il existe un corps à
+$q$ éléments, unique à isomorphisme près.  Un tel corps est un corps
+de décomposition (\refext{Alg}{décomposition}) du polynôme
+$X^q-X∈𝐅_p[X]$.
+\end{proposition2}
+\begin{proof}
+L'existence se déduit du lemme \ref{sous-corps-a-q-elements} appliqué
+à une clôture algébrique $K$ de $\FF_p$ ou simplement à un corps de
+décomposition sur $\FF_p$ de $X^q-X$.  L'unicité se déduit de même :
+tout corps fini $F$ à $q$ éléments se plonge dans la clôture
+algébrique de $\FF_p$ (car $F$ est algébrique sur $\FF_p$) ou
+simplement dans un corps de décomposition sur $\FF_p$ de $X^q-X$ (car
+$F$ est engendré par les racines de ce polynôme) et la
+proposition \ref{unicite-corps-q-elements-pour-inclusion} montre alors
+l'unicité de $F$ dans ce sur-corps qui ne dépendait pas de $F$.  La
+dernière affirmation est claire compte tenu
+de \ref{unicite-corps-q-elements-pour-inclusion}.
+\end{proof}
+
+(On verra en \refext{ACF}{remarque-isomorphisme-explicite-corps-finis} une
+façon d'obtenir un isomorphisme explicite entre des présentations
+différentes d'un même corps fini.)
+
+Dès lors que $q$ est une puissance stricte d'un nombre premier,
+l'isomorphisme n'est plus unique puisque $\Frob\colon x \mapsto x^p$
+constitue sur un corps fini à $q$ éléments un automorphisme différent
+de l'identité.
+
+On se permettra pourtant de noter, lorsque $q = p^r$ est une puissance
+d'un nombre premier, par $\FF_q$ le corps fini à $q$ éléments,
+celui-ci étant défini à isomorphisme non unique près ; ou encore, si
+un corps contient un sous-corps ayant $q$ éléments (nécessairement
+unique en tant que sous-corps, comme on l'a expliqué), on notera
+$\FF_q$ ce sous-corps.
+
+Si $q = p^r$, on notera par ailleurs $\Frob_q = (\Frob)^r \colon x
+\mapsto x^q$ l'élévation à la puissance $q$ dans n'importe quel corps
+de caractéristique $p$ : si le corps en question contient $\FF_q$,
+alors $\FF_q$ est exactement l'ensemble des points fixes de $\Frob_q$,
+et le morphisme $\Frob_q$, non content d'être $\FF_p$-linéaire, est en
+fait $\FF_q$-linéaire.  Plus généralement, on définit $\Frob_q =
+(\Frob)^r \colon x \mapsto x^q$ dans n'importe quelle $\FF_q$-algèbre.
+
+\subsubsection{} Les trois lemmes suivants, qui doivent être considérés
+comme un tout, ont pour vocation à clarifier le comportement des
+polynômes $X^q - X$ lorsque $q$ est remplacé par une certaine
+puissance de lui-même.
+
+\begin{lemme2}\label{lemme-divisibilite-x-q-r-x}
+Soient $m$ et $n$ deux entiers naturels non nuls tels que $m|n$.
+Alors :
+\begin{itemize}
+\item pour tout entier $q>1$, l'entier $q^m-1$ divise $q^n-1$,
+\item le polynôme $X^m-1$ divise $X^n-1$ (dans $\ZZ[X]$ ou, par
+conséquent, $A[X]$ pour n'importe quel anneau $A$),
+\item pour tout entier $q>1$, le polynôme $X^{q^m}-X$ divise
+$X^{q^n}-X$ (de même).
+\end{itemize}
+\end{lemme2}
+\begin{proof}
+Le premier point découle de ce que $q^n-1 = (q^m-1)(q^{n-m} + q^{n-2m}
++ \cdots + q^{2m} + q^m + 1)$, comme on le voit en dévelopant.  Le
+second découle de même de ce que $X^n-1 = (X^m-1)(X^{n-m} + X^{n-2m}
++ \cdots + X^{2m} + X^m + 1)$.  Le troisième point découle des deux
+premiers : puisque $q^m-1$ divise $q^n-1$, le polynôme $X^{q^m-1} - 1$
+divise $X^{q^n-1} - 1$, et par conséquent $X^{q^m} - X$ divise
+$X^{q^n} - X$.
+\end{proof}
+
+\begin{lemme2}\label{lemme-non-divisibilite-x-q-r-x}
+Soient $m$ et $n$ deux entiers naturels non nuls et $r$ le reste de la
+division euclidienne de $m$ par $n$ ; on suppose $r>0$.  Alors :
+\begin{itemize}
+\item pour tout entier $q>1$, le reste de la division euclidienne de
+$q^m-1$ par $q^n-1$ est $q^r-1$,
+\item il existe $g$ dans $\ZZ[X]$ tel que $X^m-1 = (X^n-1) g + (X^r-1)$,
+\item pour tout entier $q>1$, il existe $g$ dans $\ZZ[X]$ tel que
+$X^{q^m}-X = (X^{q^n}-X) g + (X^{q^r}-X)$.
+\end{itemize}
+\end{lemme2}
+\begin{proof}
+Écrivons $m = kn+r$ : le lemme \ref{lemme-divisibilite-x-q-r-x} montre
+que $q^{kn} \equiv 1 \pmod{q^n-1}$, et par conséquent $q^m - 1 \equiv
+q^r -1 \pmod{q^n-1}$ ; puisque $0 < q^r - 1 < q^n - 1$, on a le
+premier point annoncé.  Le second est rigoureusement analogue.  Le
+troisième découle des deux premiers : puisque $q^r - 1$ est le reste
+de la division euclidienne de $q^m - 1$ par $q^n - 1$, on peut écrire
+$X^{q^m-1} - 1 = (X^{q^n-1}-1) g + (X^{q^r-1}-1)$, donc $X^{q^m} - X
+= (X^{q^n}-X) g + (X^{q^r}-X)$.
+\end{proof}
+
+\begin{lemme2}\label{lemme-pgcd-x-q-r-x}
+Soient $m$ et $n$ deux entiers naturels non nuls et $d$ leur pgcd.
+Alors :
+\begin{itemize}
+\item pour tout entier $q>1$, les entiers $q^m-1$ et $q^n-1$ ont pour
+pgcd $q^d-1$ (concrètement, il existe $u,v$ entiers tels que $(q^m-1)u
++ (q^n-1)v = q^d-1$),
+\item les polynômes $X^m-1$ et $X^n-1$ de $\ZZ[X]$ engendrent l'idéal
+$(X^d-1)$ de $\ZZ[X]$ (concrètement, il existe $u,v$ de $\ZZ[X]$ tels
+que $(X^m-1)u + (X^n-1)v = X^d-1$),
+\item pour tout entier $q>1$, les polynômes $X^{q^m}-X$ et $X^{q^n}-X$
+de $\ZZ[X]$ engendrent l'idéal $(X^{q^d}-X)$ de $\ZZ[X]$
+(concrètement, il existe $u,v$ de $\ZZ[X]$ tels que $(X^{q^m}-X) u +
+(X^{q^n}-X) v = X^{q^d}-X$.
+\end{itemize}
+\end{lemme2}
+\begin{proof}
+Avant toute chose, \ref{lemme-divisibilite-x-q-r-x} assure bien que
+$q^d-1$ divise $q^m-1$ et $q^n-1$, que $X^d-1$ divise bien $X^m-1$ et
+$X^n-1$, et que $X^{q^d}-X$ divise bien $X^{q^m}-X$ et $X^{q^n}-X$.
+(Ceci justifie notamment que dire « il existe $u,v$ de $\ZZ[X]$ tels
+que $(X^m-1)u + (X^n-1)v = X^d-1$ » traduise bien le fait que $X^m-1$
+et $X^n-1$ engendrent l'idéal $(X^d-1)$, et pas un idéal plus gros, et
+de même pour les autres points.)
+
+Montrons le premier point par récurrence sur $n$.  Si $n=d$, tout est
+clair.  Sinon, soit $r$ le reste de la division euclidienne de $m$
+par $n$, qui vérifie bien sûr $r>0$.  Alors le reste de la division
+euclidienne de $q^m-1$ par $q^n-1$ vaut $q^r-1$
+d'après \ref{lemme-non-divisibilite-x-q-r-x}.  Par conséquent,
+$\pgcd(q^m-1,q^n-1) = \pgcd(q^n-1,q^r-1)$.  Comme $n$ et $r$ sont
+premiers entre eux, l'hypothèse de récurrence permet de conclure que
+ceci vaut $q^d-1$, ce qu'on voulait prouver.
+
+Montrons le second point par récurrence sur $n$.  Si $n=d$, tout est
+clair.  Sinon, soit $r$ le reste de la division euclidienne de $m$
+par $n$, qui vérifie bien sûr $r>0$.  Alors on peut écrire $X^m-1 =
+(X^n-1) g + (X^r-1)$ d'après \ref{lemme-non-divisibilite-x-q-r-x}.
+Comme $n$ et $r$ sont premiers entre eux, l'hypothèse de récurrence
+permet de trouver une écriture $X^d-1 = (X^n-1)u + (X^r-1)v$ ; en
+remplaçant $X^r-1$ par $X^m-1 - (X^n-1) g$, on trouve bien une
+écriture $X^d-1 = (X^m-1)u' + (X^n-1)v'$ comme souhaitée.
+
+Le troisième point se démontre encore par récurrence sur $n$.
+Si $n=d$, tout est clair.  Sinon, soit $r$ le reste de la division
+euclidienne de $m$ par $n$, qui vérifie bien sûr $r>0$.  Alors on peut
+écrire $X^{q^m}-X = (X^{q^n}-X) g + (X^{q^r}-X)$
+d'après \ref{lemme-non-divisibilite-x-q-r-x}.  Comme $n$ et $r$ sont
+premiers entre eux, l'hypothèse de récurrence permet de trouver une
+écriture $X^{q^d}-X = (X^{q^n}-X)u + (X^{q^r}-X)v$ ; en remplaçant
+$X^{q^r}-X$ par $X^{q^m}-X - (X^{q^n}-X) g$, on trouve bien une
+écriture $X^{q^d}-X = (X^{q^m}-X)u' + (X^{q^n}-X)v'$ comme souhaitée.
+\end{proof}
+
+\begin{proposition2}\label{inclusions-corps-finis}
+Si $q = p^r$ et $q' = p^{\prime r'}$, on a $\FF_q \subseteq \FF_{q'}$
+(au sens où $\FF_{q'}$ contient un sous-corps à $q$ éléments, qui est
+alors unique et isomorphe à $\FF_q$) si et seulement si $p = p'$ et
+$r|r'$.  Le degré de l'extension $\FF_{q'} \bo \FF_q$ est alors $r'/r$.
+
+Si $q = p^r$ et $q' = p^{r'}$ avec $\pgcd(r,r') = r_0$, alors $\FF_q
+\cap \FF_{q'} = \FF_{q_0}$ où $q_0 = p^{r_0}$ dans n'importe quel
+corps contenant des sous-corps ayant $q$ et $q'$ éléments.
+\end{proposition2}
+\begin{proof}
+Si $\FF_q \subseteq \FF_{q'}$ où $q = p^r$ et $q' = p^{\prime r'}$, on
+doit nécessairement avoir $p = p'$ car ce sont les caractéristiques de
+ces deux corps.  Par ailleurs, $\FF_{q'}$ est un espace vectoriel de
+dimension finie sur $\FF_q$, donc en notant $s$ sa dimension, on a $q'
+= q^s$, c'est-à-dire $r' = rs$ et $r|r'$ comme annoncé.
+
+Réciproquement, si $p = p'$ et $r|r'$, alors $q' = q^s$ où $s = r'/r$
+est entier, donc le lemme \ref{lemme-divisibilite-x-q-r-x} montre que
+$X^{q'} - X$ est multiple de $X^q - X$ (dans $\ZZ[X]$ et en
+particulier dans $\FF_{q'}[X]$), et comme $X^{q'}-X$ est scindé sur
+$\FF_{q'}$, le polynôme $X^q-X$ l'est aussi, ce qui montre que
+$\FF_q \subseteq
+\FF_{q'}$ d'après \ref{sous-corps-a-q-elements}.
+
+La seconde affirmation est alors claire : $\FF_q \cap \FF_{q'}$ est un
+corps fini qui contient le corps fini à $p^{r_1}$ éléments si et
+seulement si $r_1 | r$ et $r_1 | r'$, c'est-à-dire si et seulement si
+$r_1 | r_0$ où $r_0 = \pgcd(r,r')$ --- autrement dit, il s'agit
+justement de $\FF_{q_0}$.
+\end{proof}
+
+\section{Polynômes irréductibles}
+
+\subsection{Polynômes minimaux et éléments conjugués}
+
+Lorsque $x \in \FF_{q^r}$, on rappelle que le \emph{polynôme minimal}
+(\refext{Alg}{polynome-minimal}) de $x$ sur $\FF_q$ (lequel est un
+sous-corps de $\FF_{q^r}$ d'après \ref{inclusions-corps-finis}) est le
+polynôme unitaire $h \in \FF_q[X]$ engendrant l'idéal dans $\FF_q[X]$
+des polynômes $f$ tels que $f(x) = 0$, et que c'est l'unique polynôme
+unitaire irréductible dans $\FF_q[X]$ s'annulant en $x$ ; son degré
+est le degré $s = [\FF_q(x) : \FF_q]$ de $x$ sur $\FF_q$, qui divise
+le degré $r = [\FF_{q^r} : \FF_q]$ de l'extension.  De plus, dans ces
+conditions, on a $\FF_q(x) \cong \FF_q[X]/(h) \cong \FF_{q^s}$ : en
+particulier, d'après \ref{petit-theoreme-fermat}, l'élément $x$
+vérifie $x^{q^s} = x$, et $h(X) | (X^{q^s}-X)$.  Réciproquement, on
+rappelle que si $h \in \FF_q[X]$ est un polynôme irréductible
+quelconque alors $\FF_q[X]/(h)$ est un corps, et la classe $x$ de $X$
+modulo $h$ (c'est-à-dire dans $\FF_q[X]/(h) = \FF_q(x)$) a $h$ pour
+polynôme minimal.
+
+\begin{proposition2}\label{racines-polynome-minimal-corps-fini}
+Lorsque $x \in \FF_{q^r}$ a pour polynôme minimal $h$ sur $\FF_q$ et
+degré $s$ (divisant $r$), alors le polynôme $h$ est scindé sur
+$\FF_{q^r}$ et ses racines sont $x, x^q, x^{q^2}, \ldots,
+x^{q^{s-1}}$ :
+\[
+h(X) = \prod_{i=0}^{s-1} (X-\Frob_q^i(x))
+\]
+\end{proposition2}
+\begin{proof}
+Puisque $h \in \FF_q[X]$ et que $\Frob_q$ est un automorphisme de
+$\FF_{q^r}$ fixant $\FF_q$, on a $h(\Frob_q^i(x)) =
+\Frob_q^i(h(x)) = 0$ pour tout $i$, c'est-à-dire que les $x^{q^i}$
+sont racines de $h$.  Montrons maintenant que $x, x^q, \ldots,
+x^{q^{s-1}}$ sont deux à deux distincts, c'est-à-dire que l'ordre de
+$\Frob_q$ agissant sur $x$ (qui doit diviser $s$, comme on l'a
+expliqué) est exactement $s$ : or si on a $x^{q^t} = x$ pour $t \leq
+s$, on a $x \in \FF_{q^t}$ donc le degré $s$ de $x$ sur $\FF_q$
+diviserait $t$, ce qui n'est possible que pour $t=s$.  Finalement, on
+a trouvé $s$ racines distinctes dans $\FF_{q^r}$ pour un
+polynôme ($h$) de degré $s$, c'est-à-dire que ce polynôme est scindé
+avec la décomposition annoncée.
+\end{proof}
+
+Le phénomène qu'on vient de mettre en évidence, bien particulier aux
+corps finis, et qui traduira le fait que leur groupe de Galois absolu
+est abélien, est que pour tout polynôme irréductible $h \in
+\FF_q[X]$, le polynôme $h$ est scindé sur n'importe quel corps qui
+en contient une racine, autrement dit, \emph{le corps de
+rupture $\FF_q[X]/(h)$ de $h$ en est un corps de décomposition}.  En
+particulier, en utilisant \ref{inclusions-corps-finis}, $\FF_{q^r}$
+est un corps de décomposition de $h$ (supposé irréductible !) pour
+tout multiple $r$ du degré de $h$.  Si $h$ n'est pas supposé
+irréductible, il découle de ce qui vient d'être dit que \emph{son
+corps de décompossition est $\FF_{q^r}$ où $r$ est le plus petit
+commun multiple des degrés des facteurs irréductibles de $h$}.
+
+De plus, on vient de voir que l'ordre de $\Frob_q$ agissant sur $x$
+--- ou, par conséquent, sur $\FF_q(x)$ --- est exactement le degré $s$
+de $x$ sur $\FF_q$.  En utilisant le théorème de l'élément
+primitif (\refext{Alg}{element-primitif}), on peut conclure que
+$\Frob_q$ agissant sur $\FF_{q^r}$ est d'ordre exactement $r$ ; on
+fournira toutefois
+en \ref{existence-polynome-irreductible-tout-degre-corps-finis} une
+démonstration plus simple du théorème de l'élément primitif dans le
+cas particulier des corps finis.
+
+\begin{corollaire2}\label{elements-conjugues-corps-finis}
+Soient $x,x' \in \FF_{q^r}$.  Les conditions suivantes sont
+équivalentes :
+\begin{enumerate}
+\item les polynômes minimaux de $x$ et $x'$ sur $\FF_q$ sont égaux,
+\item le polynôme minimal de $x$ s'annule en $x'$,
+\item tout polynôme $f \in \FF_q[X]$ à coefficient dans $\FF_q$
+  s'annulant en $x$ s'annule aussi en $x'$,
+\item il existe $i$ (qu'on peut supposer compris entre $0$ et $r-1$)
+  tel que $x' = x^{q^i}$.
+\end{enumerate}
+\end{corollaire2}
+\begin{proof}
+L'équivalence entre les deux premières conditions (qui n'a rien de
+particulier au cas des corps finis) résulte du fait que le polynôme
+minimal d'un élément sur $\FF_q$ est l'unique polynôme unitaire
+irréductible sur $\FF_q$ s'annulant en cet élément.  L'équivalence
+avec la troisième résulte de ce que les polynômes de $\FF_q[X]$
+s'annulant en un élément de $\FF_{q^r}$ sont exactement les multiples
+du polynôme minimal de cet élément.
+
+Enfin, la proposition précédente montre que, quel que soit $x \in
+\FF_{q^r}$, les autres racines de son polynôme minimal sont justement
+les $x^{q^i}$ (pour $i$ qu'on peut supposer entre $0$ et $r-1$) : il y
+a donc équivalence entre (ii) et (iv).
+\end{proof}
+
+Des éléments $x,x' \in \FF_{q^r}$ vérifiant les conditions
+équivalentes énoncées dans le
+corollaire \ref{elements-conjugues-corps-finis} sont dits
+\emph{conjugués sur $\FF_q$}.  La première condition montre qu'il
+s'agit bien d'une relation d'équivalence, et la seconde, que tout
+élément de $\FF_{q^r}$ a un nombre de conjugués sur $\FF_q$ égal à son
+degré sur $\FF_q$.  (Cette définition et ces propriétés seront
+généralisées plus tard dans le cadre d'une extension de corps plus
+générale : cf. \refext{CG}{conjugues=racines}.)
+
+La proposition suivante généralise la dernière affirmation
+de \ref{petit-theoreme-fermat} :
+\begin{proposition2}\label{factorisation-x-q-r-x}
+La décomposition en facteurs irréductibles du polynôme $X^{q^r} - X$
+dans $\FF_q[X]$ est donnée comme le produit de tous les polynômes
+unitaires irréductibles de $\FF_q[X]$ de degré divisant $r$, chacun
+apparaissant avec multiplicité $1$.
+
+Notamment, la somme des degrés de tous les polynômes unitaires
+irréductibles de $\FF_q[X]$ de degré divisant $r$ vaut $q^r$.
+\end{proposition2}
+\begin{proof}
+Si $h \in \FF_q[X]$ est irréductible de degré $s$ avec $s|r$, alors
+il est scindé à racines simples dans $\FF_{q^r}$ d'après
+\ref{racines-polynome-minimal-corps-fini} et les remarques qui
+suivent : il s'ensuit que $h$ divise $X^{q^r} - X$ (dans
+$\FF_{q^r}[X]$ donc dans $\FF_q[X]$).  Comme tous les polynômes
+unitaires irréductibles de degré divisant $r$ dans $\FF_q[X]$ sont
+deux à deux premiers entre eux, le fait que $X^{q^r}-X$ soit multiple
+de chacun d'eux implique qu'il est multiple de leur produit.  Pour
+conclure, il reste donc à montrer l'égalité des degrés, c'est-à-dire
+la dernière affirmation de l'énoncé : or cela se voit en écrivant
+$q^r$ (le cardinal de $\FF_{q^r}$) comme somme des cardinaux de chaque
+classe de conjugaison d'éléments sur $\FF_q$ (chacune étant associée à
+un unique polynôme minimal, dont elle a un cardinal égal au degré).
+\end{proof}
+
+\begin{exemple2}\label{irreductibles-sur-f16}
+Le polynôme $X^{16}-X$ se factorise sur $\FF_2$ comme : $X^{16}-X =
+X(X+1)\penalty-100 (X^2+X+1)\penalty-100 (X^4+X+1)\penalty0
+(X^4+X^3+1)\penalty-50 (X^4+X^3+X^2+X+1)$.
+\end{exemple2}
+
+\subsubsection{}\label{definition-fonction-de-Moebius} On appelle \emph{fonction de Möbius} la fonction $\mu \colon \NN \to
+\ZZ$ définie par $\mu(n) = 0$ si $n$ est multiple du carré d'un entier
+autre que $1$ et $\mu(n) = (-1)^t$ si $n = p_1\cdots p_t$ avec
+$p_1,\ldots,p_t$ des nombres premiers deux à deux distincts (ainsi,
+$\mu(1) = 1$, $\mu(2) = -1$, $\mu(3) = -1$, $\mu(4) = 0$, $\mu(5) =
+-1$, $\mu(6) = 1$, $\mu(7) = -1$, $\mu(8) = 0$, $\mu(9) = 0$, $\mu(10)
+= 1$).  On admet le résultat suivant :
+\begin{proposition2}[théorème d'inversion de Möbius]
+Si $\Gamma$ est un groupe abélien et que $f\colon \NN_{>0} \to \Gamma$
+est une fonction quelconque, alors les deux formules suivantes sont
+équivalentes pour une fonction $g\colon \NN_{>0} \to \Gamma$ :
+\[
+g(n) = \sum_{d|n} f(d)
+\]
+\[
+f(n) = \sum_{d|n} \mu\big(\frac{n}{d}\big)\, g(d)
+\]
+\end{proposition2}
+
+\begin{corollaire2}\label{denombrement-polynomes-irreductibles-corps-finis}
+Le nombre de polynômes unitaires irréductibles de degré $n$
+sur $\FF_q$ vaut
+\[
+\frac{1}{n} \sum_{d|n} \mu\big(\frac{n}{d}\big)\, q^d
+\]
+Où $\mu$ est la fonction de Möbius.  Lorsque $n \to +\infty$ (à $q$
+fixé), ce nombre vaut $\frac{1}{n} q^n + O(q^{n/2})$.
+\end{corollaire2}
+\begin{proof}
+Pour ce qui est de la première affirmation, en notant $M(n)$ le nombre
+--- qu'on cherche à calculer --- d'unitaires irréductibles de
+degré $n$ sur $\FF_q$, la formule d'inversion de Möbius montre qu'il
+suffit de prouver $q^n = \sum_{d|n} d\,M(d)$ : or c'est justement la
+deuxième affirmation de l'énoncé de la
+proposition \ref{factorisation-x-q-r-x}.
+
+Pour ce qui est de l'estimation asymptotique, remarquons que dans la
+somme exacte, le terme $d=n$ vaut $\frac{1}{n} q^n$, le terme
+$d=\frac{n}{2}$, s'il existe (c'est-à-dire, si $n$ est pair), vaut
+$-\frac{1}{n} q^{n/2}$, et tous les autres termes, dont le nombre est
+au plus $n$, sont chacun $O(q^{n/3})$ --- leur somme est donc
+bien $O(q^{n/2})$.
+\end{proof}
+
+Même sans utiliser la formule d'inversion de Möbius, on peut au moins
+démontrer, dans le même esprit que cette estimation asymptotique :
+\begin{corollaire2}\label{existence-polynome-irreductible-tout-degre-corps-finis}
+Sur $\FF_q$, il existe au moins un polynôme irréductible de chaque
+degré $r$.  De façon équivalente, dans $\FF_{q^r}$, il existe un
+élément de degré $r$ sur $\FF_q$.
+\end{corollaire2}
+\begin{proof}
+Le nombre d'éléments de $\FF_{q^r}$ de degré $<r$ est majoré par la
+somme des cardinaux des $\FF_{q^s}$ pour $s|r$, or chacun est de
+cardinal $\leq q^{r/2}$ et leur nombre est $\leq r$, par conséquent
+cette somme de cardinaux est inférieure ou égale à $r q^{r/2}$.  Pour
+avoir la conclusion souhaitée, il suffit d'avoir $q^r > r q^{r/2}$,
+soit $q^{r/2} > r$, ce qui se produit dès que $2^r > r^2$, donc dès
+que $r > 4$.  Pour les valeurs plus petites de $r$, on constate que
+$q^4 > q^2 + q$ et $q^3 > q$ et $q^2 > q$ (et $q > 0$...) pour tout $q
+\geq 2$.
+\end{proof}
+
+On verra en \ref{cyclicite-groupe-multiplicatif-corps} un résultat
+plus fin : l'existence d'éléments ou de polynômes \emph{primitifs}.
+
+Avec les remarques qui
+suivent \ref{racines-polynome-minimal-corps-fini}, ceci montre
+notamment que $\Frob_q$ agissant sur $\FF_{q^r}$ est d'ordre
+exactement $r$.
+
+\subsection{Critères d'irréductibilité}
+
+\begin{proposition2}[critère d'irréductibilité de Rabin]\label{critere-rabin}
+Un polynôme $h \in \FF_q[X]$ de degré $r$ est irréductible si et
+seulement si il vérifie la conjonction des deux conditions
+suivantes :
+\begin{itemize}
+\item le polynôme $h$ divise $X^{q^r}-X$,
+\item le polynôme $h$ est premier avec $X^{q^s}-X$ pour tout $s$
+diviseur strict de $r$ (ou simplement les diviseurs immédiats de $r$,
+c'est-à-dire les $r/\ell$ avec $\ell$ diviseur premier de $r$).
+\end{itemize}
+\end{proposition2}
+\begin{proof}
+Si $h$ est irréductible de degré $r$, alors,
+d'après \ref{factorisation-x-q-r-x}, $h$ divise $X^{q^r}-X$, et s'il
+divise $X^{q^s}-X$ pour $s|r$, on doit avoir $r|s$, ce qui n'est
+possible que pour $s=r$ et la seconde condition est démontrée
+($h$ étant supposé irréductible, s'il ne divise pas $X^{q^s}-X$, il
+est premier avec lui).
+
+Réciproquement, si $h$ vérifie les deux conditions annoncées, et si
+$h_1$ en est un facteur irréductible, le degré $r_1$ de $h_1$ doit
+diviser $r$ d'après la première condition (toujours en
+utilisant \ref{factorisation-x-q-r-x}), et il ne peut pas être un
+diviseur strict de $r$ d'après la seconde condition (qui assure que
+$h_1$ ne divise pas $X^{q^s}-X$) : donc $r_1=r$ et $h_1=h$.  Ceci
+montre que $h$ est irréductible.
+
+Le fait qu'il suffise de tester la seconde condition pour les
+diviseurs $s$ de la forme $r/\ell$ avec $\ell$ premier résulte de ce
+que $X^{q^s}-X$ divise $X^{q^{s'}}-X$ si $s|s'$.
+\end{proof}
+
+\begin{remarques2}\label{remarques-critere-rabin}
+\begin{itemize}
+\item On ne peut pas se contenter de vérifier l'une des deux conditions
+énoncées : l'exemple du polynôme $X^6+X^5+X^4+X^3+X^2+X+1 =
+(X^3+X^2+1)\penalty-100 (X^3+X+1) \in \FF_2[X]$, qui n'est pas
+irréductible mais vérifie la première condition (il divise déjà
+$X^8-X$) montre que la première condition, seule, n'assure pas
+l'irréductibilité ; et l'exemple du polynôme $X^5 + X^4 + 1 =
+(X^2+X+1)\penalty-100 (X^3+X+1) \in \FF_2[X]$, qui n'est pas
+irréductible mais est premier à $X^2-X$ montre que la seconde
+condition, seule, n'est pas non plus suffisante.  On peut aussi donner
+l'exemple de $X^6 + X^5 + X = X (X^2+X+1) (X^3+X+1) \in \FF_2[X]$, qui
+n'est pas irréductible bien qu'il vérifie la première condition et
+aussi la seconde condition dans laquelle on a affaibli « $h$ est
+premier avec $X^{q^s}-X$ » en « $h$ ne divise pas $X^{q^s}-X$ » (pour
+tout diviseur $s$ de $r$, soit ici $s \in \{1,2,3\}$).
+\item Le critère de Rabin fournit un \emph{algorithme} permettant de
+tester l'irréductibilité d'un polynôme $h \in \FF_q[X]$ de degré $r$
+en un nombre raisonnable (i.e., polynomial\footnote{On peut par
+exemple montrer qu'il s'effectue en au pire $O(r^{2+\varepsilon})$
+opérations pour tout $\varepsilon>0$, où la constante impliquée par
+le $O$ dépend de $\varepsilon$ et $q$.} en $r$) d'opérations
+dans $\FF_q$ : en effet, la première condition du critère s'exprime
+également comme $X^{q^r} \equiv X \pmod{h}$, ce qui se teste en
+calculant $X^{q^r}$ dans $\FF_q[X]/(h)$ au moyen d'un algorithme
+d'exponentiation rapide, et la seconde condition, pour un $s$ donné,
+peut se tester au moyen de l'algorithme d'Euclide étendu (pour
+calculer le pgcd), dont la première étape consiste à calculer le reste
+de la division euclidienne de $X^{q^s}-X$ par $h$, ce qui peut de
+nouveau se faire en travaillant dans $\FF_q[X]/(h)$.
+\item Une fois qu'on dispose d'un algorithme permettant de tester
+l'irréductibilité d'un polynôme $h \in \FF_q[X]$ de degré $r$ donné,
+il est possible de \emph{générer} des polynômes irréductibles de
+degré $r$ selon le principe simple suivant : tirer un polynôme
+(unitaire) de degré $r$ au hasard, tester son irréductibilité, et
+recommencer jusqu'à trouver un polynôme irréductible.  En vertu de
+l'asymptotique trouvée
+en \ref{denombrement-polynomes-irreductibles-corps-finis}, parmi les
+$q^r$ polynômes unitaires de degré $r$ sur $\FF_q$, une proportion
+d'environ $\frac{1}{r}$ d'entre eux sont irréductibles, donc
+l'algorithme qu'on vient de décrire réussira en environ $r$ essais en
+moyenne.  Enfin, il convient de remarquer que la connaissance d'un
+polynôme $h$ irréductible de degré $r$ sur $\FF_p$ permet de
+représenter $\FF_{p^r}$ comme $\FF_p[X]/(h)$ (les calculs dans $\FF_p
+= \ZZ/p\ZZ$ sont, pour leur part, faciles) : en combinant avec ce qui
+vient d'être dit, on dispose des outils algorithmiques permettant
+d'effectuer des calculs dans tous les corps finis.
+\end{itemize}
+\end{remarques2}
+
+\begin{exemple2}\label{exemple-numerique-critere-rabin}
+Montrons sur l'exemple de $h = X^6 -2 X^4 + 3 X^3 - X^2 - X -
+2 \in \FF_7[X]$ comment on peut appliquer le critère de Rabin en
+pratique, même sans ordinateur.  On commence par calculer la table des
+restes modulo $h$ des puissances $X^7, X^{7\times 2}, X^{7\times
+3}, \ldots, X^{7\times 6}$ de l'indéterminée :
+\[
+\begin{array}{r@{\,}l}
+X^7 &\equiv 2X^5 - 3X^4 + X^3 + X^2 + 2X \pmod{h}\\
+X^{14} &\equiv -3X^5 - 2X^4 + 2X^3 + 2X^2 + 2X + 2 \pmod{h}\\
+X^{21} &\equiv -2X^5 + 3X^4 - 3X^3 - X^2 - 1 \pmod{h}\\
+X^{28} &\equiv 3X^5 - 3X^4 - 2X^3 + 2X \pmod{h}\\
+X^{35} &\equiv X^5 - 3X^4 - 2X^3 - 2X + 3 \pmod{h}\\
+X^{42} &\equiv -3X^5 + X^4 + X^3 - X^2 + X \pmod{h}\\
+\end{array}
+\]
+(la première ligne se calcule par division euclidienne de $X^7$
+par $h$, puis chaque ligne suivante en multipliant par $2X^5 - 3X^4 +
+X^3 + X^2 + 2X$ et en effectuant une nouvelle division euclidienne
+par $h$).  Il est également utile de préparer une table des valeurs du
+Frobenius sur le corps de base : ici, $a \mapsto a^7$ sur $\FF_7$ est
+bien sûr l'identité.  Au moyen de ces deux tables, on peut facilement
+élever n'importe quel polynôme à la puissance $7$ modulo $h$, donc
+calculer $X^{7^i}$ pour $i$ allant de $1$ à $6$ modulo $h$ :
+\[
+\begin{array}{r@{\,}l}
+X^7 &\equiv 2X^5 - 3X^4 + X^3 + X^2 + 2X \pmod{h}\\
+X^{7^2} &\equiv 2^7 X^{35} - 3^7 X^{28} + X^{21} + X^{14} + 2^7 X^7\\
+&\equiv -X^5 - 2X^4 + 3X^3 + 3X^2 + 3X \pmod{h}\\
+X^{7^3} &\equiv -X^{35} - 2^7 X^{28} + 3^7 X^{21} + 3^7 X^{14} + 3^7 X^7\\
+&\equiv -2X^5 + 3X^4 - X^3 - X^2 + 3X \pmod{h}\\
+X^{7^4} &\equiv -2^7 X^{35} + 3^7 X^{28} - X^{21} - X^{14} + 3^7 X^7\\
+&\equiv -3X^5 + X^4 + 2X^3 + 2X^2 \pmod{h}\\
+X^{7^5} &\equiv -3^7 X^{35} + X^{28} + 2^7 X^{21} + 2^7 X^{14} \\
+&\equiv -3 X^5 + X^4 + 2 X^3 + 2 X^2 - 2 X \pmod{h}\\
+X^{7^6} &\equiv -3^7 X^{35} + X^{28} + 2^7 X^{21} + 2^7 X^{14} - 2^7 X^7 \\
+&\equiv X \pmod{h}\\
+\end{array}
+\]
+L'égalité $X^{7^6} \equiv X \pmod{h}$ montre que la première partie du
+critère de Rabin est vérifiée.  Pour la seconde partie, il s'agit de
+continuer l'algorithme d'Euclide pour calculer le pgcd de $X^{7^2} -
+X \equiv -X^5 - 2X^4 + 3X^3 + 3X^2 + 2X$ et de $X^{7^3} - X\equiv
+-2X^5 + 3X^4 - X^3 - X^2 + 2X$ avec $h$ : or au prix de nouvelles
+divisions euclidiennes, on trouve
+\[
+\begin{array}{c}
+h \equiv -2X^4 + 2X^2 + 2X - 2 \pmod{-X^5 - 2X^4 + 3X^3 + 3X^2 + 2X}\\
+-X^5 - 2X^4 + 3X^3 + 3X^2 + 2X \equiv 2X^3 + X + 2 \pmod{-2X^4 + 2X^2 + 2X - 2}\\
+-2X^4 + 2X^2 + 2X - 2 \equiv 3 X^2 - 3 X - 2 \pmod{2X^3 + X + 2}\\
+2X^3 + X + 2 \equiv 2 X + 1 \pmod{3 X^2 - 3 X - 2}\\
+3 X^2 - 3 X - 2 \equiv 2 \pmod{2X + 1}\\
+\end{array}
+\]
+ce qui montre que $X^{7^2} - X$ est premier avec $h$, et pour ce qui
+est de $X^{7^3} - X$ :
+\[
+\begin{array}{c}
+h \equiv -2X^4 + X^2 - 3X - 2 \pmod{-2X^5 + 3X^4 - X^3 - X^2 + 2X}\\
+-2X^5 + 3X^4 - X^3 - X^2 + 2X \equiv -2X^3 + 3X - 3 \pmod{-2X^4 + X^2 - 3X - 2}\\
+-2X^4 + X^2 - 3X - 2 \equiv -2X^3 + 3X - 3 \pmod{-2X^3 + 3X - 3}\\
+-2X^3 + 3X - 3 \equiv -2 X^2 - 2 \pmod{-2X^3 + 3X - 3}\\
+-2X^3 + 3X - 3 \equiv -2 X - 3 \pmod{-2 X^2 - 2}\\
+-2 X^2 - 2 \equiv -3 \pmod{-2 X - 3}\\
+\end{array}
+\]
+--- ce qui conclut la vérification du critère de Rabin.  Tous ces
+calculs montrent donc que $h = X^6 -2 X^4 + 3 X^3 - X^2 - X - 2$ est
+irréductible dans $\FF_7[X]$.
+
+Par la suite, nous passerons normalement sous silence toutes les
+vérifications du fait qu'un polynôme univarié à coefficiens dans un
+corps fini est irréductible.
+\end{exemple2}
+
+Le critère suivant, dans le même esprit que celui de Rabin, et plus
+simple à énoncer, est plus généralement efficace quand il s'agit de
+générer des polynômes irréductibles par le procédé expliqué à la fin
+de \ref{remarques-critere-rabin} :
+\begin{proposition2}[critère d'irréductibilité de Ben-Or]\label{critere-ben-or}
+Un polynôme $h \in \FF_q[X]$ de degré $r$ est irréductible si et
+seulement si $h$ est premier avec $X^{q^i}-X$ pour tout $1 \leq i \leq
+\frac{r}{2}$ (c'est-à-dire $1 \leq i \leq \lfloor\frac{r}{2}\rfloor$
+où $\lfloor\tiret\rfloor$ désigne la partie entière).
+\end{proposition2}
+\begin{proof}
+D'après \ref{factorisation-x-q-r-x}, les facteurs irréductibles de
+$X^{q^i}-X$ pour un $1\leq i<r$ ont pour degré les diviseurs de
+ce $i$, qui sont tonc toujours strictement inférieurs à $r$ : ceci
+montre qu'un $h$ irréductible de degré $r$ est premier avec tous les
+$X^{q^i}-X$ pour $1\leq i<r$ (et en particulier $1 \leq
+i \leq \frac{r}{2}$).  Réciproquement, si $h$ a un facteur
+irréductible $h_1$ de degré $r_1<r$, alors on peut supposer
+$r_1 \leq \frac{r}{2}$ (quitte à remplacer $h_1$ par un facteur
+irréductible de $h/h_1$ si ce n'est pas le cas), et dans ce cas $h_1$
+divise $X^{q^{r_1}}-X$ donc $h$ n'est pas premier avec ce dernier.
+\end{proof}
+
+Le critère d'irréductibilité suivant utilise, pour sa part, l'algèbre
+linéaire plutôt que des manipulations de polynômes (on rappelle que
+$h \in \FF_q[X]$ est dit \emph{séparable} lorsque $h$ est à racines
+simples dans une clôture algébrique de $\FF_q$, c'est-à-dire,
+concrètement, lorsque $h$ et $h'$ sont premiers entre eux, ce qui peut
+se tester algorithmiquement par l'algorithme d'Euclide ; comme les
+corps finis sont parfaits, cela équivaut encore à dire que $h$ est
+sans facteur carré, cf. \ref{rappels-polynomes-sans-facteurs-carres-corps-finis}).
+\begin{proposition2}[critère d'irréductibilité de Butler]\label{critere-butler}
+Un polynôme $h \in \FF_q[X]$ de degré $r$ séparable est irréductible
+si et seulement si $\dim_{\FF_q} \Ker(\Frob_q - \Id) = 1$, où
+$\Frob_q \colon x \mapsto x^q$ et $\Id \colon x \mapsto x$ sont vus
+comme des applications $\FF_q$-linéaires sur $\FF_q[X]/(h)$.
+\end{proposition2}
+\begin{proof}
+Si $h$ est irréductible alors $\FF_q[X]/(h)$ est un corps (isomorphe
+à) $\FF_{q^r}$ dans lequel $\Ker(\Frob_q - \Id)$ est le sous-corps
+$\FF_q$ qui est donc de dimension $1$ comme $\FF_q$-espace vectoriel.
+
+De façon générale, quel que soit $h \in \FF_q[X]$, le $\FF_q$-espace
+vectoriel $\Ker(\Frob_q - \Id)$ contient au moins celui engendré
+par $1$, donc sa dimension est au moins $1$ : il reste à prouver que
+si $h$ est réductible cette dimension doit être strictement
+supérieure.  Si $h = h_1 h_2$ avec $h_1,h_2$ premiers entre eux, on a
+$\FF_q[X]/(h) \cong \FF_q[X]/(h_1) \times \FF_q[X]/(h_2)$ par le
+théorème chinois, donc la dimension de $\Ker(\Frob_q - \Id)$ sur tout
+cet espace vaut au moins $1+1=2$.
+\end{proof}
+
+Il sera de nouveau question de $\Ker(\Frob_q - \Id)$ (l'\emph{algèbre
+de Berlekamp} de $h$) dans la
+proposition \refext{ACF}{proposition-algorithme-berlekamp} qui généralise le
+critère ci-dessus.
+
+\begin{exemple2}\label{exemple-numerique-critere-butler}
+Reprenons l'exemple du polynôme $h = X^6 -2 X^4 + 3 X^3 - X^2 - X -
+2 \in \FF_7[X]$ de \ref{exemple-numerique-critere-rabin} en lui
+appliquant cette fois le critère de Butler : il faut d'abord vérifier
+que $h$ est séparable, c'est-à-dire, premier avec sa dérivée $h' =
+-X^5 - X^3 + 2 X^2 - 2 X - 1$, ce qui se fait au moyen de l'algorithme
+d'Euclide :
+\[
+\begin{array}{c}
+h \equiv -3 X^4 - 2 X^3 - 3 X^2 - 2 X - 2 \pmod{h'}\\
+h' \equiv -2 X^3 + 2 X^2 - X - 3 \pmod{-3 X^4 - 2 X^3 - 3 X^2 - 2 X - 2}\\
+-3 X^4 - 2 X^3 - 3 X^2 - 2 X - 2 \equiv -3 X^2 - 2 X + 2 \pmod{-2 X^3 + 2 X^2 - X - 3}\\
+-2 X^3 + 2 X^2 - X - 3 \equiv -3 X \pmod{-3 X^2 - 2 X + 2}\\
+-3 X^2 - 2 X + 2 \equiv 2\pmod{-3 X}\\
+\end{array}
+\]
+(la dernière ligne de calcul est, en fait, inutile : tout polynôme de
+coefficient constant non nul est premier avec un multiple nul de
+l'indéterminée).  On calcule alors la matrice de l'endomorphisme
+$\Frob_7 - \Id$ sur la base $1, X, X^2, \ldots, X^5$ de
+$\FF_7[X]/(h)$, en calculant successivement $X^7, X^{14}, \ldots,
+X^{35}$ modulo $h$ --- les calculs sont donc très semblables à ceux
+menés au début de \ref{exemple-numerique-critere-rabin} et conduisent
+à :
+\[
+\Frob_7 = \left(
+\begin{matrix}
+1& 0& 2&-1& 0& 3\\
+0& 2& 2& 0& 2&-2\\
+0& 1& 2&-1& 0& 0\\
+0& 1& 2&-3&-2&-2\\
+0&-3&-2& 3&-3&-3\\
+0& 2&-3&-2& 3& 1\\
+\end{matrix}
+\right)
+\;,\;\;
+\Frob_7-\Id = \left(
+\begin{matrix}
+0& 0& 2&-1& 0& 3\\
+0& 1& 2& 0& 2&-2\\
+0& 1& 1&-1& 0& 0\\
+0& 1& 2& 3&-2&-2\\
+0&-3&-2& 3& 3&-3\\
+0& 2&-3&-2& 3& 0\\
+\end{matrix}
+\right)
+\]
+(Les coefficients de la première matrice sont les coefficients des
+restes de $X^7, X^{14}, X^{21},\ldots, X^{35}$ modulo $h$, comme
+calculés en \ref{exemple-numerique-critere-rabin}.)  On calcule le
+rang de cette deuxième matrice en appliquant l'algorithme du pivot de
+Gauß : on se convainc ainsi que les cinq colonnes non-nulles sont
+linéairement indépendantes, c'est-à-dire que le rang est $5$, ce qui
+prouve bien $\dim_{\FF_7} \Ker(\Frob_7 - \Id) = 1$, donc $h$ est bien
+irréductible.
+\end{exemple2}
+
+\subsection{Polynômes irréductibles et extensions}
+
+\subsubsection{} Nous étudions maintenant ce que devient un polynôme
+irréductible sur un corps fini lorsque ce dernier est remplacé par une
+extension (d'abord de degré divisant le degré du polynôme, puis
+premier avec lui, et enfin en corollaire dans le cas général).
+
+\begin{proposition2}\label{scindage-partiel-polynomes-corps-finis}
+Soit $f \in \FF_q[X]$ irréductible de degré $r$, et $s$ un diviseur
+de $r$.  Alors $f$ vu dans $\FF_{q^s}[X]$ est produit de $s$ facteurs
+irréductibles chacun de degré $r/s$.  Si $h$ est l'un de ces facteurs,
+alors tous sont donnés par les $\Frob_q^i(h)$ (où par là on désigne le
+polynôme de même degré que $h$, dont les coefficients sont image de
+ceux de $h$ par $\Frob_q^i$, sans faire agir ce dernier sur
+l'indéterminée) pour $i$ allant de $0$ à $s-1$.
+\end{proposition2}
+\begin{proof}[Première démonstration]
+Puisque $f$ est irréductible sur $\FF_q$, on
+sait (\ref{factorisation-x-q-r-x}) qu'il divise $X^{q^r}-X$, qui
+s'écrit encore $X^{(q^s)^{r/s}}-X$, par conséquent (toujours
+d'après \ref{factorisation-x-q-r-x}) sur $\FF_{q^s}$ le polynôme $f$
+est produit de facteurs irréductibles distincts de degrés
+divisant $r/s$.  Mais par ailleurs $f$ est premier avec $X^{q^t}-X$
+pour tout diviseur strict $t$ de $r$ (\ref{critere-rabin}) : en
+particulier avec les $X^{(q^s)^t}-X$ pour $t$ diviseur strict
+de $r/s$ ; ceci montre que les facteurs irréductibles de $f$ sont de
+degré exactement $r/s$, et par conséquent ils sont bien au nombre
+de $s$.  Si $h$ est un quelconque de ces facteurs irréductibles, qu'on
+choisira unitaire, alors $\Frob_q^i(h)$ est encore, pour chaque $i$
+entre $0$ et $s-1$, un facteur irréductible de degré $r/s$ de $h$ (car
+$\Frob_q$ est un automorphisme de $\FF_q$).  Reste à savoir que tous
+ces facteurs sont distincts (donc premiers entre eux) : or si $h$
+était laissé stable par un $\Frob_q^i$ avec $0<i<s$, il serait à
+coefficients dans un $\FF_{q^{s'}}[t]$ avec $s'$ diviseur strict
+de $s$, dans lequel il serait certainement irréductible, mais c'est
+impossible car on vient de voir que les facteurs irréductibles de $f$
+dans $\FF_{q^{s'}}[t]$ sont de degré $r/s' > r/s$.
+\end{proof}
+\begin{proof}[Seconde démonstration]
+Soit $h$ un facteur irréductible de $f$ dans $\FF_{q^s}[X]$, et $x$
+une racine de $h$ dans $\FF_{q^r}$ (qui existe puisque $f$, donc $h$,
+est scindé sur $\FF_{q^r}$).  Le degré de $x$, c'est-à-dire de
+$\FF_q(x) = \FF_{q^r}$, sur $\FF_q$ vaut $r$, et par conséquent
+(\ref{inclusions-corps-finis} ou \refext{Alg}{multiplicativité degré})
+son degré sur $\FF_{q^s}$ vaut $r/s$ : c'est donc le degré de $h$
+(polynôme minimal de $x$ sur $\FF_{q^s}$).  On a vu
+en \ref{racines-polynome-minimal-corps-fini} que les racines de $f$
+(dans $\FF_{q^r}$) sont les $\Frob_q^i(x)$ pour $i$ allant de $0$
+à $r-1$, et que celles de $h$ sont les $(\Frob_{q^s})^j(x)
+= \Frob_q^{js}(x)$ pour $j$ allant de $0$ à $(r/s)-1$.  Pour $i$
+allant de $0$ à $s-1$, le polynôme $\Frob_q^i(h) \in \FF_{q^s}[X]$
+s'annule en $\Frob_q^i(x)$ et en tous les $\Frob_q^{i+js}(x)$ ; il est
+irréductible puisque $\Frob_q^i$ est un automorphisme de
+$\FF_{q^s}[X]$ (et que $h$ est irréductible), et tous ces polynômes
+$\Frob_q^i(h)$ sont premiers entre eux puisque leurs racines dans
+$\FF_{q^r}$, où ils se scindent, sont disjointes : par conséquent, $f$
+est bien égal, à une constante près, au produit des $\Frob_q^i(h)$
+(pour $i$ allant de $0$ à $s-1$).
+\end{proof}
+
+Voir \ref{descindage-polynomes-tours-corps-finis} pour une sorte de
+réciproque de cette affirmation.
+
+\begin{proposition2}\label{polynomes-restent-irreductibles-corps-finis}
+Soit $h \in \FF_q[X]$ irréductible de degré $r$, et soit $s$ premier
+avec $r$.  Alors $h$ vu dans $\FF_{q^s}[X]$ est encore irréductible.
+\end{proposition2}
+\begin{proof}[Première démonstration]
+D'après le critère de Rabin (\ref{critere-rabin}), le polynôme $h$
+divise $X^{q^r}-X$, et est premier avec $X^{q^t}-X$ pour tout $t$
+diviseur strict de $r$ : on veut prouver la même chose en remplaçant
+$q$ par $q^s$.  Le fait que $X^{q^r}-X$ divise $X^{(q^s)^r}-X$ (et
+donc que $h$ divise ce dernier) résulte du
+lemme \ref{lemme-divisibilite-x-q-r-x} ; par ailleurs, un diviseur de
+$h$ et de $X^{q^{st}}-X$ devrait diviser à la fois $X^{q^r}-X$ et
+$X^{q^{st}}-X$ donc leur pgcd, qui vaut $X^{q^t}-X$
+d'après \ref{lemme-pgcd-x-q-r-x} (puisque le pgcd de $r$ et $st$
+est $t$).
+\end{proof}
+\begin{proof}[Seconde démonstration]
+Soit $h_1$ un facteur irréductible de $h$ dans $\FF_{q^s}[X]$, et $x$
+une racine de $h_1$ dans $\FF_{q^{rs}}$ (qui existe puisque $h$ est
+scindé sur $\FF_{q^r}$, donc dans $\FF_{q^{rs}}$, donc $h_1$ est
+scindé dans $\FF_{q^{rs}}$).  Alors $(\Frob_{q^s})^i(x)
+= \Frob_q^{is}(x)$ est racine de $h_1$ pour tout $i$.  Or, $s$ étant
+premier avec $r$, l'entier $is$ prend toutes les valeurs possibles
+modulo $r$, donc $\Frob_q^{is}(x)$ parcourt toutes les racines de $h$
+(cf. \ref{racines-polynome-minimal-corps-fini}) : ceci montre que
+toute racine de $h$ est racine de $h_1$ et finalement $h = h_1$ est
+irréductible dans $\FF_{q^s}[X]$.
+\end{proof}
+
+\begin{corollaire2}\label{corollaire-scindage-partiel-polynomes-corps-finis}
+Soit $f \in \FF_q[X]$ irréductible de degré $r$, et $s > 0$ un entier
+naturel, et soit $d = \pgcd(r,s)$.  Alors $f$ vu dans $\FF_{q^s}[X]$
+est produit de $d$ facteurs irréductibles chacun de degré $r/d$.  Si
+$h$ est l'un de ces facteurs, alors tous sont donnés par les
+$\Frob_q^i(h)$ (où par là on désigne le polynôme de même degré
+que $h$, dont les coefficients sont image de ceux de $h$ par
+$\Frob_q^i$, sans faire agir ce dernier sur l'indéterminée) pour $i$
+allant de $0$ à $d-1$.
+\end{corollaire2}
+\begin{proof}
+C'est une conséquence immédiate des
+propositions \ref{scindage-partiel-polynomes-corps-finis} et \ref{polynomes-restent-irreductibles-corps-finis},
+en appliquant la première pour décrire $f$ dans $\FF_{q^d}[X]$ et la
+seconde pour voir que chacun des facteurs irréductibles reste
+irréductible en passant de $\FF_{q^d}[X]$ à $\FF_{q^s}[X]$ (vu que
+$s/d$ est premier avec $r$).
+\end{proof}
+
+La proposition suivante doit être vue comme un complément
+à \ref{scindage-partiel-polynomes-corps-finis} :
+
+\begin{proposition2}\label{descindage-polynomes-tours-corps-finis}
+Soit $h \in \FF_{q^s}[X]$ unitaire irréductible de degré $t$.  Alors
+le polynôme $f = \prod_{i=0}^{s-1}\Frob_q^i(h)$, de degré $st$,
+appartient à $\FF_q[X]$, et il est irréductible si et seulement si le
+ppcm des degrés sur $\FF_q$ des coefficients de $h$ est égal à $s$.
+\end{proposition2}
+\begin{proof}
+Le fait que $f$ appartienne à $\FF_q[X]$ vient de ce que $\Frob_q(f) =
+f$ (on rappelle que $\Frob_q$ opère uniquement sur les coefficients
+des polynômes), comme il résulte aisément de $\Frob_q^s(h) = h$.
+
+Dire que le ppcm des degrés sur $\FF_q$ des coefficients de $h$ est
+égal à $s$ signifie (cf. \ref{racines-polynome-minimal-corps-fini})
+que $\Frob_q$ a pour période exactement $s$ en agissant sur $h$,
+c'est-à-dire que tous les $\Frob_q^i(h)$ (pour $i$ allant de $0$
+à $s-1$) sont distincts et donc, étant unitaires et irréductibles
+sur $\FF_{q^s}$, premiers entre eux.  Si c'est le cas, alors $f$ est
+irréductible sur $\FF_q$, car aucun sous-ensemble non trivial de ses
+facteurs irréductibles $\Frob_q^i(h)$ sur $\FF_{q^s}$ n'est stable
+par $\FF_q$ donc ne définit de polynôme de $\FF_q[X]$.
+Réciproquement, si $f$ est irréductible dans $\FF_q[X]$, il a $st$
+racines distinctes dans $\FF_{q^{st}}$, donc tous les $\Frob_q^i(h)$
+sont distincts.
+\end{proof}
+
+On étudiera en \refext{ACF}{remarque-tours-corps-finis} la question du rapport
+entre les présentations de $\FF_{q^{st}}$, dans les conditions de la
+proposition précédente, données par $\FF_q[X]/(f)$ et par
+$\FF_{q^s}[X]/(h)$.
+
+\section{Éléments primitifs et groupe multiplicatif}
+
+\subsection{Éléments primitifs}
+
+\begin{théorème2}\label{cyclicite-groupe-multiplicatif-corps}
+Tout sous-groupe fini du groupe multiplicatif d'un corps est cyclique.
+En particulier, le groupe multiplicatif d'un corps fini est cyclique.
+\end{théorème2}
+
+\begin{démo}
+Soient $K$ un corps et $G⊆K^×$ un sous-groupe fini.  Pour tout entier
+$n$, l'ensemble $G[n]$ des éléments de $G$ d'ordre divisant $n$ est de
+cardinal au plus $n$ car il est inclus dans l'ensemble des racines
+dans $K$ du polynôme $X^n-1$.  La conclusion résulte donc du lemme
+suivant.
+\end{démo}
+
+\begin{lemme2}\label{lemme-detection-groupes-cycliques}
+Soit $G$ un groupe fini non nécessairement abélien d'ordre $n$ tel que
+pour tout $d$ divisant $n$ on ait
+\[\# G[d]≤d\]
+en notant $G[d]$ l'ensemble des éléments d'ordre divisant $d$.
+Alors $G$ est cyclique.
+\end{lemme2}
+
+\begin{démo}
+Pour tout $d$ divisant $n$, notons $X_d$ l'ensemble des éléments
+d'ordre exactement $d$.  On souhaite montrer que $X_n$ est non vide.
+Commençons par montrer que si un $X_d$ est non vide, il est d'ordre
+$φ(d)$.  En effet, si $x∈X_d$, l'ensemble à $d$ éléments
+$\{1,x,\dots,x^{d-1}\}$ est inclus dans — donc égal à — $G[d]$.  Pour
+un tel $d$, $G[d]$ est cyclique d'ordre $d$ et $X_d$ est l'ensemble de
+ses générateurs, donc de cardinal $φ(d)$.  Il résulte de la formule
+$∑_{d|n} φ(d)=n$ et de l'égalité $G=∐_{d|n} X_d$ (le symbole $\coprod$
+désignant la réunion disjointe) que chaque $X_d$ est non vide. En
+particulier c'est le cas de $X_n$.
+\end{démo}
+
+\begin{definition2}\label{element-primitif-corps-fini}
+Un élément $x \in \FF_q^\times$ qui engendre le groupe multiplicatif
+$\FF_q^\times$ est dit \emph{primitif}.
+\end{definition2}
+
+Le théorème \ref{cyclicite-groupe-multiplicatif-corps} affirme donc
+qu'il existe dans (le groupe multiplicatif de) tout corps fini $\FF_q$
+des éléments primitifs, et leur nombre est alors $\varphi(q-1)$
+(nombre de générateurs d'un groupe cyclique d'ordre $q-1$), où
+$\varphi$ désigne la fonction indicatrice d'Euler.  Plus généralement,
+le nombre d'éléments d'ordre exactement $d$ dans $\FF_q^\times$ est
+$\varphi(d)$ si $d|(q-1)$ et $0$ sinon (comparer avec la démonstration
+du lemme \ref{lemme-detection-groupes-cycliques}).
+
+\begin{remarques2}\label{elements-et-polynomes-primitifs}
+Si $x \in \FF_{q^r}^\times$ est primitif, alors tout élément conjugué
+à $x$ sur $\FF_q$ (cf. \ref{elements-conjugues-corps-finis} et les
+remarques qui suivent) est encore primitif (en effet, l'ordre
+multiplicatif d'un élément est préservé par l'automorphisme de
+corps $\Frob_q \colon z \mapsto z^q$).  Par ailleurs, le degré de $x$
+sur $\FF_q$ est alors exactement $r$ (et non un diviseur strict $s$
+de $r$) : en effet, si on avait $x \in \FF_{q^s}$ avec $s<r$ alors
+toutes les puissances de $x$ appartiendraient à $\FF_{q^s}$,
+contredisant l'hypothèse que $x$ soit primitif.
+
+Il est donc raisonnable d'appeler aussi primitif le polynôme minimal
+commun sur $\FF_q$ de $x$ et de ses conjugués.  Autrement dit, un
+polynôme primitif sur $\FF_q$ est un polynôme irréductible de
+degré $r$ sur $\FF_q$ dont les racines dans $\FF_{q^r}$ sont
+primitives.
+
+Puisqu'il existe $\varphi(q^r-1)$ éléments primitifs dans $\FF_{q^r}$
+et que la classe de conjugaison de chacun comporte exactement $r$
+éléments et définit un unique polynôme primitif unitaire, on en déduit
+qu'il existe $\frac{1}{r}\varphi(q^r-1)$ polynômes primitifs unitaires
+de degré $r$ sur $\FF_q$.  Ce résultat, à comparer
+avec \ref{denombrement-polynomes-irreductibles-corps-finis}, fournit
+une nouvelle démonstration du fait qu'il existe des polynômes
+irréductibles de degré arbitraire sur un corps fini (et qu'il existe
+dans $\FF_{q^r}$ des éléments de degré $r$ sur $\FF_q$).
+
+Signalons la conjecture d'Artin : si $ℓ$ est un nombre premier,
+il existe une infinité de nombres premiers $p$ tels
+que $ℓ$ soit primitif modulo $p$, c'est-à-dire tel que l'image 
+de $ℓ$ dans $𝐅_p$ soit un élément primitif. \XXX
+%cf. p. ex. http://www.mast.queensu.ca/~murty/mi.dvi
+\end{remarques2}
+
+\begin{proposition2}\label{2-primitif-mod-p}
+Si $p$ un nombre premier de la forme
+$4ℓ+1$ où $ℓ$ est un nombre premier, alors $2$ est primitif modulo
+$p$.
+\end{proposition2}
+
+Cette proposition s'applique par exemple à $p=13,29$ ou $53$.
+
+\begin{démo}
+Un nombre $a$ est primitif modulo $p$ si pour tout
+premier $p'$ tel que $p$ soit congru à $1$ modulo $p'$, 
+$a^{(p-1)/p'}$ n'est pas congru à $1$ modulo $p$. 
+Sous l'hypothèse de la proposition, $p-1$ a deux diviseurs
+premiers : $2$ et $ℓ$. Puisque $ℓ$ est impair,
+$4ℓ+1$ congru à $5$ modulo $8$, de sorte que
+(\refext{ACF}{formule-complementaire}) $2^{(p-1)/2}$ est congru à $-1$
+modulo $p$. Enfin, $2^{(p-1)/ℓ}=2^4≡1$ modulo $p$ entraîne $p=3$ ou $5$.
+\end{démo}
+
+\begin{remarque2}
+On ne sait pas s'il existe une infinité de nombres premiers
+de la forme $(p-1)/4$. Par contre, la méthode dite du « crible »
+permet de montrer qu'il existe une infinité de premiers $p$
+tels que $(p-1)/4$ soit un produit de deux nombres premiers
+plus grands que $p^θ$ où $θ$ est une constante strictement supérieure
+à $⅓$. On peut en déduire (Heath-Brown) que l'un des trois entiers $2$, $3$ et $5$
+est primitif pour une infinité de nombres premiers.
+\end{remarque2}
+
+\begin{exemples2}\label{primitifs-sur-f16}
+\begin{itemize}
+\item Le polynôme irréductible $h = X^4+X+1 \in \FF_2[X]$ est primitif
+(sur $\FF_2$), c'est-à-dire qu'une quelconque de ses racines engendre
+$\FF_{16}^\times$.  Pour se convaincre à la fois du fait qu'il est
+irréductible et qu'il est primitif, on peut par exemple calculer les
+puissances successives de la classe $x$ de $X$ modulo $h$, soit
+$x^0=1$, $x^1=x$, $x^2$, $x^3$, $x^4=x+1$, $x^5=x^2+x$, $x^6=x^3+x^2$,
+$x^7=x^3+x+1$, $x^8=x^2+1$, $x^9=x^3+x$, $x^{10}=x^2+x+1$,
+$x^{11}=x^3+x^2+x$, $x^{12}=x^3+x^2+x+1$, $x^{13}=x^3+x^2+1$,
+$x^{14}=x^3+1$ et $x^{15}=1$ : le fait qu'on ait obtenu un groupe
+cyclique à $15$ éléments, c'est-à-dire tous les éléments non nuls de
+$\FF_2[X]/(h)$, montre d'une part que l'ensemble des éléments non nuls
+de $\FF_2[X]/(h)$ est un groupe (donc que $\FF_2[X]/(h)$ est un corps,
+c'est-à-dire que $h$ est irréductible) et d'autre part que $x$ y est
+primitif, c'est-à-dire que $h$ est primitif.
+\item Le polynôme irréductible $h = X^4+X^3+X^2+X+1 \in \FF_2[X]$,
+bien qu'irréductible, n'est pas primitif.  En effet, on a $X^5 \equiv
+X \pmod{h}$, c'est-à-dire que la classe $x$ de $X$ dans $\FF_2[X]/(h)$
+est d'ordre $5$, et cette classe n'engendre donc pas
+$\FF_{16}^\times$.
+\end{itemize}
+\end{exemples2}
+
+Ces exemples ont notamment pour but de souligner le fait que tous les
+polynômes irréductibles ne sont pas nécessairement primitifs ou que,
+de façon équivalente, le fait qu'un élément $x \in \FF_{q^r}$ soit de
+degré $r$ sur $\FF_q$ ne suffit pas à entraîner qu'il soit primitif.
+(De fait, c'était déjà clair sur les dénombrements qu'on a obtenus :
+dans $\FF_{16}$ il y a $16-4 = 12$ éléments de degré $4$ sur $\FF_2$,
+dont seulement $\varphi(15) = 8$ sont primitifs, c'est-à-dire qu'il y
+a parmi les polynômes unitaires de degré $4$ sur $\FF_2$ un total de
+$\frac{12}{4} = 3$ polynômes irréductibles dont $\frac{8}{4} = 2$ sont
+primitifs.)
+
+\begin{lemme2}\label{somme-x-s-dans-f-q}
+Si $s$ est un entier naturel, alors $\sum_{x\in\FF_q} x^s$ vaut $-1$
+si $s$ est non-nul \emph{et} multiple de $q-1$, et $0$ sinon (on fait
+la convention $0^0 = 1$).
+\end{lemme2}
+\begin{proof}
+Si $s=0$, la somme $\sum_{x\in\FF_q} x^s = \sum_{x\in\FF_q} 1$
+vaut $q$, c'est-à-dire $0$ dans $\FF_q$.  Supposons maintenant $s>0$ :
+alors $\sum_{x\in\FF_q} x^s = \sum_{x\in\FF_q^\times} x^s$, et en
+appelant $g$ un élément primitif de $\FF_q$, cette somme s'écrit
+encore $\sum_{i=0}^{q-2} g^{si}$.  Si $g^s = 1$, ce qui se produit
+exactement lorsque $s$ est multiple de $q-1$, la somme vaut $q-1$,
+c'est-à-dire $-1$ dans $\FF_q$.  Sinon, on a $\sum_{i=0}^{q-2} g^{si}
+= \frac{g^{s(q-1)}-1}{g^s-1} = 0$.
+\end{proof}
+
+\subsection{Polynômes cyclotomiques et corps finis}
+
+\subsubsection{} On rappelle que les polynômes cyclotomiques
+$\Phi_n \in \ZZ[X]$ sont les uniques polynômes unitaires à
+coefficients rationnels (et en fait, entiers) vérifiant pour tout $n$
+la relation $X^n-1 = \prod_{d|n} \Phi_d(X)$ (le produit étant pris sur
+tous les $d$ divisant $n$).  On peut aussi écrire $\Phi_n(X)
+= \prod_\zeta (X-\zeta)$ pour $\zeta$ parcourant l'ensemble des
+racines primitives $n$-ièmes de l'unité dans une extension quelconque
+de $\QQ$ les contenant.  Les $\Phi_n$ sont irréductibles dans $\ZZ[X]$
+(et deux à deux distincts, donc deux à deux premiers entre eux), et le
+degré de $\Phi_n$ est $\varphi(n)$.  La formule $\Phi_n(X)
+= \prod_\zeta (X-\zeta)$ pour $\zeta$ parcourant l'ensemble des
+racines primitives $n$-ièmes de l'unité est encore valable dans
+n'importe quel corps, de caractéristique ne divisant pas $n$, où il
+existe une --- et donc $\varphi(n)$ --- racine primitive $n$-ième de
+l'unité.
+
+Si $q$ et $n$ sont premiers entre eux où $q$ est une puissance d'un
+nombre premier $p$, considérons un $r$ tel que $n|(q^r-1)$
+(c'est-à-dire $q^r \equiv 1 \pmod{n}$ ; un tel $r$ existe évidemment :
+par exemple l'ordre multiplicatif de $q$ modulo $n$ convient) ; dans
+ces conditions, si $\xi$ est un élément primitif de $\FF_{q^r}$, il
+est facile de voir que $\zeta = \xi^{(q^r-1)/n}$ est d'ordre
+multiplicatif exactement $n$ dans $\FF_{q^r}$, c'est-à-dire, est une
+racine primitive $n$-ième de l'unité.  Dans ces conditions (lorsque
+$n|(q^r-1)$), on a encore $\Phi_n(X) = \prod_\zeta (X-\zeta)$ dans
+$\FF_{q^r}$, où $\zeta$ parcourt les racines primitives $n$-ièmes de
+l'unité dans $\FF_{q^r}$, c'est-à-dire les $\varphi(n)$ éléments
+d'ordre exactement $n$ dans $\FF_{q^r}^\times$.  En particulier, les
+$\Phi_n$ pour $n$ premier avec $q$ sont encore deux à deux premiers
+entre eux dans $\FF_q[X]$.
+
+On a, de façon analogue à \ref{factorisation-x-q-r-x} :
+\begin{proposition2}\label{factorisation-phi-q-r-1}
+La décomposition en facteurs irréductibles du polynôme
+$\Phi_{q^r-1}(X)$ dans $\FF_q[X]$ est donnée comme le produit de tous
+les polynômes unitaires primitifs de $\FF_q[X]$ de degré $r$ (au
+nombre de $\frac{1}{r}\varphi(q^r-1)$,
+cf. \ref{elements-et-polynomes-primitifs}), chacun apparaissant avec
+multiplicité $1$.
+\end{proposition2}
+\begin{proof}
+D'après ce qui a été dit, $\Phi_{q^r-1}$ est scindé sur $\FF_{q^r}$ et
+ses racines sont exactement les éléments primitifs de $\FF_{q^r}$
+(chacune avec multiplicité $1$) ; et sur $\FF_q$ on a vu que les
+polynômes minimaux de ces éléments primitifs de $\FF_{q^r}$ sont les
+polynômes unitaires primitifs de degré $r$ sur $\FF_q$.
+\end{proof}
+
+\begin{exemple2}
+Dans $\FF_2$, le polynôme $\Phi_{15}(X) = X^8 - X^7 + X^5 - X^4 + X^3
+- X + 1 \in \ZZ[X]$ se factorise comme $(X^4 + X + 1)\penalty-100 (X^4
++ X^3 + 1)$ : ces deux facteurs sont les $\frac{1}{4} \varphi(15) = 2$
+polynômes primitifs de degré $4$ sur $\FF_2$.  (Comparer
+avec \ref{primitifs-sur-f16}.)
+\end{exemple2}
+
+Plus généralement :
+\begin{proposition2}\label{factorisation-phi-n}
+Soit $n$ un entier naturel premier avec $q$ (où $q$ est une puissance
+d'un nombre premier).  Alors la décomposition en facteurs
+irréductibles du polynôme $\Phi_n(X)$ dans $\FF_q[X]$ est formée de
+$\frac{1}{r}\varphi(n)$ facteurs irréductibles chacun de degré $r$, où
+$r$ est l'ordre multiplicatif de $q$ modulo $n$ (c'est-à-dire le plus
+petit entier naturel tel que $q^r \equiv 1 \pmod{n}$).
+
+En particulier, (toujours sous l'hypothèse que $n$ et $q$ sont
+premiers entre eux, cf. \ref{irreductibilite-phi-n-complement})
+$\Phi_n(X)$ est irréductible dans $\FF_q[X]$ exactement lorsque $q$
+engendre le groupe multiplicatif $(\ZZ/n\ZZ)^\times$.
+\end{proposition2}
+\begin{proof}
+Soit $r$ l'ordre multiplicatif de $q$ modulo $n$.  Il existe alors
+dans $\FF_{q^r}$ une racine primitive $n$-ième de l'unité $\zeta$ :
+ansi, $\Phi_n$ est scindé sur $\FF_{q^r}$ et on peut écrire $\Phi_n(X)
+= \prod (X-\zeta^j)$ pour $j$ parcourant (les $\varphi(n)$ éléments
+de) $(\ZZ/n\ZZ)^\times$.  Le degré de $\zeta^j$ sur $\FF_q$ (pour
+$j \in (\ZZ/n\ZZ)^\times)$) est le plus petit $i$ tel que
+$\zeta^{j\,q^i} = \zeta^j$, c'est-à-dire tel que $j q^i \equiv
+j \pmod{n}$, ce qui équivaut à $q^i \equiv 1 \pmod{n}$ (puisque $j$
+est inversible modulo $n$), c'est donc exactement $r$.  Ainsi,
+$\Phi_n$ est scindé sur $\FF_{q^r}$, et les polynômes minimaux sur
+$\FF_q$ de ses racines sur $\FF_{q^r}$ sont chacun de degré $r$ : ceci
+prouve que $\Phi_n$ s'écrit sur $\FF_q$ comme produit de
+$\frac{1}{r}\varphi(n)$ polynômes irréductibles de degré $r$.
+
+La dernière affirmation signifie simplement que $q$ engendre le groupe
+multiplicatif $(\ZZ/n\ZZ)^\times$ exactement lorsque son ordre
+multiplicatif modulo $n$ est $\varphi(n)$.
+\end{proof}
+
+On peut dire (cf. les remarques
+suivant \ref{racines-polynome-minimal-corps-fini}) que le corps de
+décomposition de $\Phi_n$ sur $\FF_q$ (toujours sous l'hypothèse que
+$n$ n'est pas multiple de $p$) est $\FF_{q^r}$ où $r$ est l'ordre
+multiplicatif de $q$ modulo $n$.  Ce corps de décomposition, qui est
+le corps de rupture d'un quelconque des facteurs irréductibles (tous
+de degré $r$) de $\Phi_n$ sur $\FF_q$, peut se noter $\FF_q(\zeta_n)$,
+en désignant par $\zeta_n$ une racine primitive $n$-ième de l'unité
+dans $\FF_{q^r}$.  Il faut cependant se garder de croire que les
+différents choix possibles de $\zeta_n$ soient interchangeables (plus
+précisément, qu'ils seraient conjugués sous l'action de $\Frob_q$) :
+même si le corps $\FF_q(\zeta_n) = \FF_{q^r}$ engendré par $\zeta_n$
+est le même quel que soit le choix effectué, le polynôme minimal de
+$\zeta_n$ sur $\FF_q$, lui, ne l'est pas (c'est justement l'un
+quelconque des $\frac{1}{r} \varphi(n)$ facteurs irréductibles
+de $\Phi_n$) ; ceci diffère de la situation sur $\QQ$ où toutes les
+racines primitives $n$-ièmes de l'unité sont interchangeables
+(précisément, on dira qu'elles sont conjuguées par le groupe de
+Galois), non seulement elles engendrent le même corps $\QQ(\zeta_n)$
+mais aussi elles ont le même polynôme minimal sur $\QQ$, qui est
+justement $\Phi_n$.
+
+\begin{proposition2}
+Soit $h$ un polynome irréductible unitaire sur $\FF_q$, autre que $X$.
+Alors il existe un unique $n$ premier à $q$ tel que $h$
+divise $\Phi_n$ : ce $n$ divise $q^r-1$ où $r$ est le degré de $h$.
+Il s'agit exactement de l'ordre multiplicatif d'une racine
+(quelconque) de $h$ dans $\FF_{q^r}$.
+\end{proposition2}
+\begin{proof}
+On a $X^{q^r-1}-1 = \prod_{n|(q^r-1)} \Phi_n(X)$ par définition
+des $\Phi_n$, donc $X^{q^r}-X = X\,\prod_{n|(q^r-1)} \Phi_n(X)$.
+D'après \ref{factorisation-x-q-r-x}, le polynôme irréductible $h$
+divise ce produit : il doit donc diviser un des $\Phi_n$ avec
+$n|(q^r-1)$.  Comme les $\Phi_n$ pour $n$ premier à $q$ sont premiers
+entre eux, il ne peut en diviser un autre.  Enfin, dire qu'une racine
+de $h$ (dans $\FF_{q^r}$) est racine de $\Phi_n$ signifie précisément
+que son ordre multiplicatif est exactement $n$.
+\end{proof}
+
+\begin{exemples2}
+\begin{itemize}
+\item Le polynôme $\Phi_5(X) = X^4+X^3+X^2+X+1 \in \ZZ[X]$ demeure
+irréductible dans $\FF_2$ car $2$ engendre $(\ZZ/5\ZZ)^\times$.  Il
+n'est, naturellement, pas primitif (puisque ses racines dans
+$\FF_{2^4}$ sont d'ordre $5$ et non $15$).  On retrouve-là un exemple
+déjà donné en \ref{primitifs-sur-f16}.
+\item Le polynôme $\Phi_{9}(X) = X^6 + X^3 + 1 \in \ZZ[X]$
+demeure irréductible dans $\FF_2$ car $2$
+engendre $(\ZZ/9\ZZ)^\times$.  Il n'est, naturellement, pas primitif
+(puisque ses racines dans $\FF_{2^6}$ sont d'ordre $9$ et non $63$).
+\item Le polynôme $\Phi_{17}(X) = X^{16} + X^{15} + \cdots + X + 1 \in
+\ZZ[X]$ se factorise dans $\FF_2$ comme produit de deux facteurs de
+degré $8$ puisque $2$ est d'ordre $8$ dans $(\ZZ/17\ZZ)^\times$ (on a
+$2^8 \equiv 1 \pmod{17}$).  À savoir : $\Phi_{17}(X) =
+(X^8+X^5+X^4+X^3+1)\penalty-100 (X^8+X^7+X^6+X^4+X^2+X+1)$.  Aucun de
+ces facteurs, naturellement, n'est primitif (puisque leurs racines
+sont toutes d'ordre $17$ et non $2^8-1 = 255$).
+\end{itemize}
+\end{exemples2}
+
+\subsubsection{} Lorsque $n$ n'est plus supposé premier avec $p$
+(i.e., avec $q$), les choses sont très différentes, et le polynôme
+$\Phi_n$ n'est généralement plus séparable sur $\FF_q$ comme on va le
+voir.  Par exemple, il est facile de se convaincre par récurrence
+sur $k$ que $\Phi_{p^k}(X) = (X-1)^{(p-1)p^{k-1}}$ sur $\FF_p$ (ou
+sur $\FF_q$, donc).
+
+\begin{proposition2}\label{factorisation-phi-n-inseparable}
+Si $n = p^k m$ où $m$ n'est pas multiple de $p$, alors $\Phi_n(X)
+= \Phi_m(X)^{(p-1)p^{k-1}}$ dans $\FF_p[X]$ (donc dans $\FF_q[X]$).
+En particulier, sauf éventuellement dans le cas où $p=2$ et $k=1$, le
+polynôme $\Phi_n(X)$ n'est ni séparable ni irréductible
+sur $\FF_q[X]$.
+\end{proposition2}
+\begin{proof}
+On procède par récurrence sur $k$ et, à $k$ fixé, par récurrence
+sur $m$.  On a d'une part $X^{p^k m} - 1 = (X^m-1)^{p^k}
+= \prod_{d|m}\Phi_d(X)^{p^k}$ et d'autre part $X^{p^k m} - 1
+= \prod_{d|p^k m} \Phi_d(X) = \prod_{d|m}
+(\Phi_d(X)\, \prod_{\ell=1}^k \Phi_{p^\ell d}(X))$.  Les hypothèses
+des récurrences permettent de remplacer chaque $\Phi_{p^\ell d}(X)$
+par $\Phi_d(X)^{(p-1)p^{\ell-1}}$ sauf le dernier
+($\ell=k$ et $d=m$) : pour montrer qu'on a bien aussi $\Phi_{p^k m}(X)
+= \Phi_m(X)^{(p-1)p^{k-1}}$, il suffit donc de montrer que
+$\prod_{d|m}\Phi_d(X)^{p^k} = \prod_{d|m}
+(\Phi_d(X)\, \prod_{\ell=1}^k \Phi_d(X)^{(p-1)p^{\ell-1}})$.  Or cela
+résulte du fait que $1 + \sum_{\ell=1}^k (p-1)p^{\ell-1} = p^k$.
+\end{proof}
+
+\begin{proposition2}\label{irreductibilite-phi-n-complement}
+Si $q$ est une puissance d'un nombre premier $p$ et $n$ est un entier
+naturel, le polynôme cyclotomique $\Phi_n$ est irréductible
+dans $\FF_q$ si et seulement si :
+\begin{itemize}
+\item le nombre $q$ engendre le groupe multiplicatif
+$(\ZZ/n\ZZ)^\times$ (ce qui sous-entend que $q$ est premier
+avec $n$), \emph{ou bien}
+\item on a $n=2m$ avec $m$ impair, et $p=2$, et $q$ engendre le groupe
+multiplicatif $(\ZZ/m\ZZ)^\times$.
+\end{itemize}
+\end{proposition2}
+\begin{proof}
+D'après \ref{factorisation-phi-n-inseparable}, on sait que si $n$ est
+multiple de $p$ avec $p>2$, ou que $n$ est multiple de $4$ lorsque
+$p=2$, alors $\Phi_n$ n'est pas irréductible modulo $p$ (donc
+dans $\FF_q$).  Lorsque $n$ est premier avec $q$, la
+proposition \ref{factorisation-phi-n} donne le premier cas.  Reste
+enfin le cas où $n = 2m$ avec $m$ impair et $p=2$ : dans ce cas
+$\Phi_n(X) = \Phi_m(X)$ modulo $2$, donc la
+proposition \ref{factorisation-phi-n} donne de nouveau le résultat.
+\end{proof}
+
+\begin{exemples2}
+\begin{itemize}
+\item Modulo $2$, les polynômes $\Phi_{2m}(X)$ et $\Phi_m(X)$
+(pour $m$ impair) sont toujours égaux.  (En fait, dans $\ZZ[X]$, on a
+$\Phi_{2m}(X) = \Phi_m(-X)$ pour $m$ impair, puisque les racines
+primitives $2m$-ièmes de l'unité sont les $-\zeta$ avec $\zeta$ racine
+primitive $m$-ième de l'unité.)  Ensuite, toujours modulo $2$ et avec
+$m$ impair, on a $\Phi_{4m}(X) = \Phi_m(X)^2$.
+\item Le polynôme $\Phi_8(X) = X^4 + 1$, bien qu'irréductible dans
+$\ZZ[X]$ ou $\QQ[X]$, n'est irréductible dans \emph{aucun}
+$\FF_q[X]$ : en effet, en caractéristique $p=2$, on a $\Phi_8 =
+(X-1)^4$, et en caractéristique $p\neq 2$, on a vu
+en \ref{factorisation-phi-n} que pour que $\Phi_8$ soit irréductible
+dans $\FF_q$ il faut (et il suffit) que $q$ engendre
+$(\ZZ/8\ZZ)^\times$, or ce dernier n'est pas cyclique (il a quatre
+éléments tous d'ordre divisant $2$) : donc $\Phi_8$ se scinde (en
+quatre facteurs de degré $1$) pour $q \equiv 1 \pmod{8}$, et se
+factorise en deux facteurs de degré $2$ pour tout autre $q$
+impair. (\XXX Peut-on être un chouïa plus explicite sur la
+factorisation de $\Phi_8$ modulo $p$ ?)
+\item Si $n$ est multiple de deux nombres premiers impairs distincts
+$\ell_1,\ell_2$, alors, de même, $\Phi_n$, bien qu'irréductible dans
+$\ZZ[X]$ ou $\QQ[X]$, n'est irréductible dans aucun $\FF_q$ : en
+effet, en caractéristique $\ell_1$ ou $\ell_2$, le polynôme $\Phi_n$
+n'est pas irréductible (il est une puissance parfaite) ; et en toute
+autre caractéristique, on sait que pour que $\Phi_n$ soit irréductible
+dans $\FF_q$ il faut (et il suffit) que $q$ engendre
+$(\ZZ/n\ZZ)^\times$, or ce dernier n'est pas cyclique car le théorème
+chinois assure qu'on peut l'écrire comme produit de deux groupes
+d'ordres pairs (par exemple $(\ZZ/n\ZZ)^\times \cong
+(\ZZ/n_1\ZZ)^\times \times (\ZZ/n_2\ZZ)^\times$ où $n_1 = \ell_1^k$ et
+$n_2$ est premier avec $\ell_1$).
+\end{itemize}
+\end{exemples2}
+
+\subsubsection{Éléments primitifs modulo $n$} On dit qu'un élément
+$g \in \ZZ/n\ZZ$ est \emph{primitif} modulo $n$ lorsque
+$g$ est premier avec $n$ (c'est-à-dire $g \in
+(\ZZ/n\ZZ)^\times$) et que $g$ engendre le groupe
+multiplicatif $(\ZZ/n\ZZ)^\times$.  (Lorsque $n$ est
+premier, cette terminologie est cohérente avec celle introduite
+en \ref{element-primitif-corps-fini}.)  Autrement dit, dire qu'il
+existe des éléments primitifs modulo $n$ signifie que
+$(\ZZ/n\ZZ)^\times$ est cyclique, et lorsqu'il en
+existe, il en existe exactement $\varphi(\varphi(n))$.
+
+On rappelle ou admet le résultat suivant :
+\begin{proposition2}
+\begin{itemize}
+\item Si $p$ est un nombre premier impair, alors
+  $(\ZZ/p\ZZ)^\times$ est cyclique, i.e., il existe des éléments
+  primitifs modulo $p$.  (Il en existe exactement $\varphi(p-1)$.)
+\item Si $p$ est un nombre premier impair et $k\geq 2$, alors
+  $(\ZZ/p^k\ZZ)^\times$ est cyclique, i.e., il existe des éléments
+  primitifs modulo $p^k$.  (Il en existe exactement
+  $\varphi(p^{k-1}(p-1))$.)  Plus précisément : $g$ est primitif
+  modulo $p^k$ si et seulement si il l'est modulo $p^2$.
+\item Si $p=2$ et $1\leq k\leq 2$, alors
+  $(\ZZ/2^k\ZZ)^\times$ est (trivialement) cyclique.
+\item Si $p=2$ et $k \geq 3$, alors
+  $(\ZZ/2^k\ZZ)^\times$ \emph{n'est pas} cyclique : il est produit
+  d'un groupe cyclique d'ordre $2$ engendré par $-1$ et d'un groupe
+  cyclique d'ordre $2^{k-2}$ engendré par $5$ (l'ordre maximal
+  possible d'un élément est $2^{k-2}$).
+\item Si $n$ n'est pas de la forme $2$, $4$, $p^k$ ou $2 p^k$
+  avec $p$ premier impair, alors $(\ZZ/n\ZZ)^\times$ \emph{n'est pas}
+  cyclique : il peut s'écrire comme produit de deux groupes d'ordre
+  pair.
+\end{itemize}
+\end{proposition2}
+
+Par ailleurs, on admet provisoirement le théorème suivant, qui sera
+démontré en \XXX :
+\begin{theoreme2}[Dirichlet]
+Si $b \in (\ZZ/n\ZZ)^\times$, alors il existe un nombre premier $p$
+tel que $p \equiv b \pmod{n}$.
+\end{theoreme2}
+
+On peut alors remarquer :
+\begin{proposition2}
+Pour tout entier naturel $n$, il existe un nombre premier $p$ (ou, de
+façon équivalente, une puissance $q$ d'un nombre premier) tel que
+$\Phi_n$ soit irréductible dans $\FF_p$ (resp., dans $\FF_q$) si, et
+seulement si, $n$ vaut $2$, $4$, $\ell^k$ ou $2\ell^k$ pour $\ell$
+premier impair.
+\end{proposition2}
+\begin{proof}
+Démontrons le « si » : si $n$ est d'une des formes indiquées, alors
+$(\ZZ/n\ZZ)^\times$ est cyclique, donc il existe un élément $g \in
+(\ZZ/n\ZZ)^\times$ qui soit primitif, et d'après le théorème de
+Dirichlet, on peut supposer que $g \equiv p \pmod{n}$ avec $p$
+premier, et d'après \ref{factorisation-phi-n} le polynôme $\Phi_n$ est
+irréductible modulo $p$.
+
+Montrons maintenant le « seulement si » : si $\Phi_n$ est irréductible
+dans $\FF_q$, on sait d'après \ref{irreductibilite-phi-n-complement}
+que soit $q$ est premier avec $n$ et primitif modulo $n$ soit $n=2m$
+avec $m$ impair et $q = 2^r$ est primitif modulo $m$.  Dans le premier
+cas, $n$ vaut $2$, $4$, $\ell^k$ ou $2\ell^k$ avec $\ell$ premier
+impair, et dans le second, $m$ vaut $\ell^k$ avec $\ell$ premier
+impair, donc $n=2m$ est bien de la forme $2\ell^k$ avec $\ell$ premier
+impair.
+\end{proof}
+
+\subsection{Trace et norme}
+
+On renvoie à \refext{Alg}{trace-et-norme} pour les généralités sur la
+trace et la norme dans une algèbre quelconque sur un corps.  On se
+préoccupera ici d'une extension $\FF_{q^r}\bo \FF_q$ de corps finis :
+la \emph{trace} $\Tr_{\FF{q^r}\bo\FF_q}(x)$,
+la \emph{norme} $\N_{\FF{q^r}\bo\FF_q}(x)$, et le \emph{polynôme
+caractéristique} $\chi_{\FF{q^r}\bo\FF_q}(x,X)$ d'un élément
+$x \in \FF_{q^r}$ sont respectivement la trace, la norme, et le
+polynôme caractéristique de l'application $\FF_q$-linéaire $z \mapsto
+xz$ de multiplication par $x$ sur $\FF_{q^r}$, ce dernier étant vu
+comme un $\FF_q$-espace vectoriel de dimension $r$.
+
+\begin{proposition2}\label{trace-et-norme-corps-finis}
+Soit $x \in \FF_{q^r}$ : alors on a
+\[\chi_{\FF{q^r}\bo\FF_q}(x,X) = \prod_{i=0}^{r-1} (X-\Frob_q^i(x))\]
+et en particulier
+\[\Tr_{\FF{q^r}\bo\FF_q}(x) = \sum_{i=0}^{r-1} \Frob_q^i(x)\]
+\[\N_{\FF{q^r}\bo\FF_q}(x) = \prod_{i=0}^{r-1} \Frob_q^i(x) = x^{(q^r-1)/(q-1)}\]
+\end{proposition2}
+\begin{proof}
+Considérons d'abord le cas où $x$ engendre $\FF_{q^r}$ sur $\FF_q$,
+c'est-à-dire que son degré est $r$.  Alors on a vu
+en \ref{elements-conjugues-corps-finis} que les conjugués de $x$ sont
+justement les $\Frob_q^i(x)$ pour $i\in\{0,\ldots,r-1\}$, le polynôme
+$\prod_{i=0}^{r-1} (X-\Frob_q^i(x))$ étant alors le polynôme minimal
+de $x$.  Puisqu'il est de degré $r$, c'est aussi son polynôme
+caractéristique, ce qui montre la première formule dans le cas
+particulier considéré.
+
+Dans le cas où $x$ est de degré $s<r$, on décompose l'extension
+$\FF_{q^r}\bo\FF_q$ en deux extensions $\FF_q(x)\bo\FF_q$
+(c'est-à-dire $\FF_{q^s}\bo\FF_q$) et $\FF_{q^r}\bo\FF_q(x)$, de
+degrés respectifs $s$ et $r/s$.  On a
+$\chi_{\FF_{q^r}\bo\FF_q(x)}(x,X) = (X-x)^{r/s}$.
+D'après \refext{Alg}{composition-trace-norme}
+et \refext{Alg}{Norme=pol-car}, on a $\chi_{\FF_{q^r}\bo\FF_q}(x,X)
+= \N_{\FF_q(x)[X]\bo\FF_q[X]} (\chi_{\FF_{q^r}\bo\FF_q(x)}(x,X))
+= \N_{\FF_q(x)[X]\bo\FF_q[X]}(X-x)^{r/s}
+= \chi_{\FF_q(x)\bo\FF_q}(x,X)^{r/s}$.  Or d'après le cas déjà
+démontré, $\chi_{\FF_q(x)\bo\FF_q}(x,X) = \prod_{i=0}^{s-1}
+(X-\Frob_q^i(x))$ : on a donc $\chi_{\FF_{q^r}\bo\FF_q}(x,X)
+= \prod_{i=0}^{s-1} (X-\Frob_q^i(x))^{s/r} = \prod_{i=0}^{r-1}
+(X-\Frob_q^i(x))$ en se rappelant que $\Frob_q^s(x) = x^{q^s} = x$.
+Ceci démontre la première formule en général.  Les autres formules
+s'en déduisent immédiatement.
+\end{proof}
+
+\begin{proposition2}\label{surjectivite-trace-et-norme}
+Soit $\FF_{q^r}\bo\FF_q$ une extension de corps finis.  Les
+applications $\Tr_{\FF_{q^r}\bo\FF_q} \colon \FF_{q^r}\to\FF_q$ et
+$\N_{\FF_{q^r}\bo\FF_q} \colon \FF_{q^r}\to\FF_q$ sont surjectives.
+De plus, si $g \in \FF_{q^r}$ est primitif, alors
+$\N_{\FF_{q^r}\bo\FF_q}(g) \in \FF_q$ est primitif.
+\end{proposition2}
+\begin{proof}
+La trace $\Tr_{\FF_{q^r}\bo\FF_q} \colon \FF_{q^r}\to\FF_q$ étant
+$\FF_q$-linéaire, il suffit pour montrer qu'elle est surjective de
+montrer qu'elle n'est pas identiquement nulle.  Or en tant que
+polynôme à coefficients dans $\FF_q$ (et évalué sur $\FF_{q^r}$), la
+trace est donnée par $X + X^q + X^{q^2} + \cdots + X^{q^{r-1}}$ : ce
+polynôme étant de degré $q^{r-1}$ (et non identiquement nul), il ne
+peut pas s'annuler en tout point de $\FF_{q^r}$, ce qu'on voulait.
+
+La norme $\N_{\FF_{q^r}\bo\FF_q} \colon \FF_{q^r}\to\FF_q$ est donnée
+par $x \mapsto x^{(q^r-1)/(q-1)}$.  La valeur $0$ étant manifestement
+atteinte, la norme est surjective lorsque tout élément de
+$\FF_q^\times$ est atteint.  Or $\FF_{q^r}^\times$ est un groupe
+cyclique d'ordre $q^r-1$ (\ref{cyclicite-groupe-multiplicatif-corps}),
+et $\FF_q^\times$ est son unique sous-groupe d'ordre $q-1$ : si $g$
+est un générateur de $\FF_{q^r}^\times$, alors
+$\N_{\FF_{q^r}\bo\FF_q}(g) = g^{(q^r-1)/(q-1)}$ est d'ordre
+exactement $q-1$, donc il engendre $\FF_q^\times$, ce qui montre à la
+fois la surjectivité et le fait que l'élément annoncé est primitif.
+\end{proof}
+
+\subsection{Polynômes de Conway}
+
+Le choix d'un polynôme $h$ irréductible de degré $r$ donné sur $\FF_p$
+étant loin d'être unique
+(cf. \ref{denombrement-polynomes-irreductibles-corps-finis}), même si
+on demande qu'il soit primitif
+(cf. \ref{elements-et-polynomes-primitifs}), la présentation de
+$\FF_{p^r}$ comme $\FF_p[X]/(h)$ ne l'est pas plus.  Il est parfois
+utile par exemple dans un logiciel de calcul formel devant manipuler
+$\FF_{p^r}$, de fixer une fois pour toutes une présentation
+particulière de chaque corps fini de façon à définir une notation
+standard pour ses éléments.  On pourrait pour cela choisir
+arbitrairement un polynôme unitaire irréductible de chaque degré sur
+chaque $\FF_p$ (comme le plus petit lexicographiquement), mais il
+s'avère souhaitable de faire des choix possédant certaites
+compatibilités d'un $\FF_q$ à un autre : c'est ce que réalisent les
+polynômes de Conway.
+
+Introduisons d'abord une terminologie temporaire pour la condition de
+compatibilité qui va nous occuper :
+
+\begin{definition2}\label{familles-compatibles-polynomes-conway}
+Soit $p$ un nombre premier.  On dit qu'une famille $h_1,\ldots,h_N$ de
+polynômes de $\FF_p[X]$, avec $h_n$ unitaire de degré $n$,
+est \emph{compatible au sens de Conway} lorsque :
+\begin{itemize}
+\item pour chaque $1\leq n\leq N$, le polynôme $h_n$ est primitif
+(cf. \ref{elements-et-polynomes-primitifs}),
+\item pour tout $m$ divisant $n$ entre $1$ et $N$, la norme
+$\N_{\FF_{p^n}\bo\FF_{p^m}}(x) = x^{(p^n-1)/(p^m-1)}$ de $\FF_{p^n}$ à
+$\FF_{p^m}$ d'une racine quelconque $x$ de $h_n$ dans $\FF_{p^n}$ est
+une racine de $h_m$ (autrement dit, $h_n$ divise
+$h_m(X^{(p^n-1)/(p^m-1)})$, cf. \ref{trace-et-norme-corps-finis}).
+\end{itemize}
+\end{definition2}
+
+(Dans la deuxième condition, le choix de la racine $x$ de $h_n$ est
+sans importance : dans tous les cas, le corps $\FF_p(x)$ est isomorphe
+à $\FF_p[X]/(h_n)$, et dire que la norme $x^{(p^n-1)/(p^m-1)}$ de $x$
+est racine de $h_m$ signifie que $h_m(X^{(p^n-1)/(p^m-1)}) \equiv
+0 \pmod{h_n}$.)
+
+\begin{proposition2}\label{existence-polynomes-conway}
+Soit $p$ un nombre premier, et $h_1,\ldots,h_{n-1}$ une famille de
+polynômes de $\FF_p[X]$, avec $h_i$ unitaire de degré $i$, compatible
+au sens de Conway.  Alors il existe $h_n$ unitaire de degré $n$ tel
+que $h_1,\ldots,h_n$ soit encore compatible au sens de Conway.
+\end{proposition2}
+\begin{proof}
+Fixons une présentation quelconque de $\FF_{p^n}$.
+
+Montrons dans un premier temps qu'on peut choisir, pour chaque $m$
+allant de $1$ à $n-1$, une racine $x_m$ de $h_m$ dans $\FF_{p^n}$, de
+façon à avoir la compatibilité suivante : si $\ell|m$ alors
+$x_m^{(p^m-1)/(p^\ell-1)} = x_\ell$.  On définit les $x_m$ par
+récurrence sur $m$.  Supposons les $x_\ell$ déjà choisis pour
+$\ell<m$.  Si $z$ est une racine quelconque de $h_m$ dans $\FF_{p^n}$,
+la condition de compatibilité des $h_m$ signifie que pour tout
+$\ell|m$ on a $z^{(p^m-1)/(p^\ell-1)} = x_\ell^{p^{j_\ell}}$ pour un
+certain $j_\ell \in \ZZ/\ell\ZZ$.  La compatibilité supposée sur
+les $x_\ell$ (par récurrence) assure que si $k|\ell|m$ alors
+$x_{k}^{p^{j_k}} = z^{(p^m-1)/(p^{k}-1)} = (z^{(p^m-1)/(p^\ell-1)})
+^{(p^\ell-1)/(p^{k}-1)} = (x_\ell^{p^{j_\ell}})
+^{(p^\ell-1)/(p^{k}-1)} = (x_\ell^{(p^\ell-1)/(p^{k}-1)})
+^{p^{j_\ell}} = x_{k}^{p^{j_\ell}}$, donc (l'élément $x_k$ étant de
+degré $k$ sur $\FF_p$) on a $j_\ell \equiv j_k \pmod{k}$.  Le théorème
+chinois garantit alors qu'il existe $j \in \ZZ/m\ZZ$ tel que $j \equiv
+j_\ell \pmod{\ell}$ pour tout $\ell|m$.  On pose $x_m = z^{p^{-j}}$ :
+on a alors $x_m^{(p^m-1)/(p^\ell-1)} = x_\ell^{p^{-j} \cdot p^{j_\ell}}
+= x_\ell$, comme souhaité.
+
+Soit maintenant $g$ un élément primitif de $\FF_{p^n}$, de sorte que
+$\FF_{p^n}^\times$ est isomorphe à $\ZZ/(p^n-1)\ZZ$ par $i \mapsto
+g^i$.  Pour chaque $m$ divisant $n$, l'élément $g^{(p^n-1)/(p^m-1)}$
+est primitif dans $\FF_{p^m}$ (cf. \ref{surjectivite-trace-et-norme}).
+Écrivons $x_m = g^{i_m(p^n-1)/(p^m-1)}$ avec $i_m \in \ZZ/(p^m-1)\ZZ$,
+et même $i_m$ inversible (c'est-à-dire premier avec $p^m-1$) puisque
+$x_m$ est primitif dans $\FF_{p^m}$.  Si $\ell|m$ alors la
+compatibilité $x_m^{(p^m-1)/(p^\ell-1)} = x_\ell$ obtenue au
+paragraphe précédent signifie que $(g^{i_m(p^n-1)/(p^m-1)})
+^{(p^m-1)/(p^\ell-1)} = g^{i_\ell(p^n-1)/(p^\ell-1)}$ donc $i_m \equiv
+i_\ell \pmod{p^\ell-1}$.  Le théorème chinois (avec le fait que
+$\pgcd(p^\ell-1, p^m-1) = p^{\pgcd(\ell,m)}-1$) garantit alors qu'il
+existe $i \in \ZZ/(p^n-1)\ZZ$ inversible (c'est-à-dire premier avec
+$p^n-1$) tel que $i \equiv i_m \pmod{p^m-1}$ pour tout $m|n$.  On
+définit $x_n = g^i$ : alors $x_n$ est primitif car $i$ est inversible,
+et $x_n^{(p^n-1)/(p^m-1)} = x_m$ pour tout $m|n$.  En appelant $h_n$
+le polynôme minimal de $x_n$, le polynôme $h_n$ vérifie toutes les
+compatibilités demandées.
+\end{proof}
+
+\begin{definition2}\label{definition-polynomes-conway}
+Soit $p$ un nombre premier.  On introduit l'ordre total sur $\FF_p$
+donné par $0 < 1 < 2 < \cdots < (p-1)$, et l'ordre total sur les
+polynômes unitaires de degré $n$ de $\FF_p[X]$ (« ordre
+lexicographique alterné ») donné par $X^n - a_1 X^{n-1} + \cdots +
+(-1)^n a_n < X^n - b_1 X^{n-1} + \cdots + (-1)^n b_n$ si et seulement
+si $a_i < b_i$ pour le plus petit $i$ tel que $a_i \neq b_i$.
+
+On définit alors par récurrence sur l'entier naturel non nul $n$
+le \emph{polynôme de Conway} de degré $n$ sur $\FF_p$ comme le plus
+petit polynôme unitaire $h_n$ de degré $n$, pour l'ordre introduit
+ci-dessus, tel que la famille $h_1,\ldots,h_n$ soit compatible au sens
+de Conway (\ref{familles-compatibles-polynomes-conway}).
+
+On appelle \emph{élément de Conway} de $\FF_{p^n}$ tout élément de ce
+dernier qui est racine de $h_n$.
+\end{definition2}
+
+L'existence de $h_n$ est garantie par la
+proposition \ref{existence-polynomes-conway}.  Le choix du polynôme le
+plus petit pour l'ordre lexicographique alterné est simplement une
+manière de fixer les choix effectués : la condition intéressante de
+compatibilité est celle explicitée
+en \ref{familles-compatibles-polynomes-conway}.  Un élément de Conway
+est primitif (il y en a $n$ dans $\FF_{p^n}$, mais ils sont
+conjugués), et sa norme à n'importe quel sous-corps est encore un
+élément de Conway.
+
+Le polynôme $h_1$ vaut $X - g$ où $g$ est le plus petit élément
+primitif de $\ZZ/p\ZZ$ (pour l'ordre $0<1<\cdots<(p-1)$).  C'est pour
+que la classe $x$ de $X$ dans $\FF_p[X]/(h_1)$ soit cet élément $g$
+(et non son opposé) qu'on a fait la convention de signes particulière
+de l'ordre lexicographique \emph{alterné}.
+
+Le calcul algorithmique du polynôme de Conway $h_n$ (connaissant les
+$h_m$ avec $m$ divisant $n$) peut se faire selon essentiellement deux
+stratégies :
+\begin{itemize}
+\item énumérer les polynômes unitaires de degré $n$ dans l'ordre
+lexicographique alterné jusqu'à trouver un polynôme primitif et
+vérifiant la compatibilité demandée avec les $h_m$, ou bien
+\item choisir une présentation quelconque de $\FF_{p^n}$, et dans
+celle-ci, énumérer (au moyen d'un élément primitif de $\FF_{p^n}$) les
+éléments dont la norme dans chaque $\FF_{p^m}$ pour $m|n$ est un
+élément de Conway, et choisir celui dont le polynôme minimal est le
+plus petit pour l'ordre lexicographique alterné.
+\end{itemize}
+La première stratégie applique directement la
+définition \ref{familles-compatibles-polynomes-conway}, tandis que la
+seconde fonctionne comme l'explique la preuve de la
+proposition \ref{existence-polynomes-conway}.  La première est plus
+appropriée quand $n$ est peu divisible, tandis que la seconde est plus
+efficace si $n$ a beaucoup de diviseurs (donc que les conditions de
+compatibilités sont fortes).
+
+À titre d'exemple, le tableau suivant donne les quelques premiers
+polynômes de Conway pour $p\leq 7$ :
+\begin{center}
+\begin{tabular}{|c|c|c|}
+\hline
+$p=2$&$p^n=2$&$h_1 = X + 1$\\
+&$p^n=4$&$h_2 =  X^2 + X + 1$\\
+&$p^n=8$&$h_3 =  X^3 + X + 1$\\
+&$p^n=16$&$h_4 =  X^4 + X + 1$\\
+&$p^n=32$&$h_5 =  X^5 + X^2 + 1$\\
+&$p^n=64$&$h_6 =  X^6 + X^4 + X^3 + X + 1$\\
+&$p^n=128$&$h_7 =  X^7 + X + 1$\\
+&$p^n=256$&$h_8 =  X^8 + X^4 + X^3 + X^2 + 1$\\
+&$p^n=512$&$h_9 =  X^9 + X^4 + 1$\\
+&$p^n=1024$&$h_{10} =  X^{10} + X^6 + X^5 + X^3 + X^2 + X + 1$\\
+\hline
+$p=3$&$p^n=3$&$h_1 = X + 1$\\
+&$p^n=9$&$h_2 =  X^2 + 2 X + 2$\\
+&$p^n=27$&$h_3 =  X^3 + 2 X + 1$\\
+&$p^n=81$&$h_4 =  X^4 + 2 X^3 + 2$\\
+&$p^n=243$&$h_5 =  X^5 + 2 X + 1$\\
+&$p^n=729$&$h_6 =  X^6 + 2 X^4 + X^2 + 2 X + 2$\\
+\hline
+$p=5$&$p^n=5$&$h_1 = X + 3$\\
+&$p^n=25$&$h_2 = X^2 + 4 X + 2$\\
+&$p^n=125$&$h_3 = X^3 + 3 X + 3$\\
+&$p^n=625$&$h_4 = X^4 + 4 X^2 + 4 X + 2$\\
+\hline
+$p=7$&$p^n=7$&$h_1 = X + 4$\\
+&$p^n=49$&$h_2 = X^2 + 6 X + 3$\\
+&$p^n=343$&$h_3 = X^3 + 6 X^2 + 4$\\
+\hline
+\end{tabular}
+\end{center}
+
+
+\ifx\danslelivre\undefined
+\end{document}
+\fi