diff options
author | Fabrice (iLiburu) <Fabrice.Orgogozo@gmail.com> | 2011-01-05 10:51:46 +0100 |
---|---|---|
committer | Fabrice (iLiburu) <Fabrice.Orgogozo@gmail.com> | 2011-01-05 10:51:46 +0100 |
commit | 9b397c6baf243cfab623ede077eff43b67f0d05f (patch) | |
tree | bf934a1dd51c9555c9ce0668bb262038b95be28a /chapitres/corps-finis.tex | |
parent | 71624bddf4e7e63397a9af8213153bdbdb06a3ba (diff) | |
download | galois-9b397c6baf243cfab623ede077eff43b67f0d05f.tar.gz galois-9b397c6baf243cfab623ede077eff43b67f0d05f.tar.bz2 galois-9b397c6baf243cfab623ede077eff43b67f0d05f.zip |
renommage massif : séparation des fichiers de configuration des chapitres etc.
Diffstat (limited to 'chapitres/corps-finis.tex')
-rw-r--r-- | chapitres/corps-finis.tex | 1746 |
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 |