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

1 files changed, 1549 insertions, 0 deletions

diff --git a/chapitres/algo-corps-finis.tex b/chapitres/algo-corps-finis.tex
new file mode 100644
index 0000000..1f61155
--- /dev/null
+++ b/chapitres/algo-corps-finis.tex
@@ -0,0 +1,1549 @@
+\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{Algorithmique des corps finis}
+
+\externaldocument{extensions-algebriques}
+\externaldocument{corps-finis}
+\externaldocument{correspondance-galois}
+
+\begin{document}
+\maketitle
+\tableofcontents
+\else
+\chapter{Algorithmique des corps finis}
+\fi
+
+
+\section{Calculs de racines carrées, équations quadratiques}\label{equations-quadratiques-corps-finis}
+
+\subsection{Le caractère quadratique}
+
+\begin{definition2}\label{definition-caractere-quadratique}
+Soit $q$ une puissance d'un nombre premier impair.  On
+appelle \emph{caractère quadratique} sur $\FF_q$ la fonction
+$a \mapsto a^{(q-1)/2}$.  On note $\FF_q^{\times2}$ l'ensemble des
+éléments de $\FF_q^\times$ qui sont des carrés.
+\end{definition2}
+
+\begin{proposition2}\label{denombrement-carres-f-q}
+Si $q$ est une puissance d'un nombre premier impair, alors le caractère
+quadratique ne prend sur $\FF_q^\times$ que les valeurs $+1$ et $-1$,
+et on a $a \in \FF_q^{\times2}$ si et seulement si $a^{(q-1)/2} =
++1$ ; de plus, $\# \FF_q^{\times2} = \frac{1}{2}(q-1)$.
+\end{proposition2}
+\begin{proof}
+L'application $z \mapsto z^2$, vue comme un morphisme
+$\FF_q^\times \to \FF_q^\times$, a pour noyau $\{\pm 1\}$ (de
+cardinal $2$), et pour image $\FF_q^{\times2}$, donc
+$2\, \#\FF_q^{\times2} = \#\FF_q^{\times}$ : ceci montre la dernière
+affirmation.
+
+Si $e = a^{(q-1)/2}$ avec $a \in \FF_q^\times$, alors $e^2 = a^{q-1} =
+1$, donc $e$ vaut $+1$ ou $-1$.
+
+Si $a = b^2$ avec $b \in \FF_q^\times$, alors $a^{(q-1)/2} = b^{q-1} =
++1$.  On a donc montré que sur tout élément de $\FF_q^{\times2}$ le
+caractère quadratique vaut $+1$ : comme on vient de voir qu'il y a
+$\frac{1}{2}(q-1)$ tels éléments et que le polynôme $X^{(q-1)/2} - 1$
+(de degré $\frac{1}{2}(q-1)$) n'est pas nul, il ne peut s'annuler en
+aucun autre point de $\FF_q$ : on voit donc que réciproquement si
+$a^{(q-1)/2} = +1$ alors $a \in \FF_q^{\times2}$.
+\end{proof}
+
+On pouvait également démontrer ce résultat en utilisant un élément
+primitif $g$ (cf. \refext{Fin}{cyclicite-groupe-multiplicatif-corps}) : les
+éléments de $\FF_q^{\times2}$ sont ceux qui s'écrivent $g^{2i}$ avec
+$i$ entier (et bien défini modulo $\frac{1}{2}(q-1)$).
+
+\begin{corollaire2}\label{produits-de-non-carres-dans-f-q}
+Un produit $ab$ dans $\FF_q$ est un carré \emph{si et seulement si}
+les deux facteurs $a,b$ sont soit tous deux des carrés soit tous deux
+des non-carrés.
+\end{corollaire2}
+\begin{proof}
+Cela découle de \ref{denombrement-carres-f-q} et du fait que le
+caractère quadratique est un morphisme multiplicatif : $(ab)^{(q-1)/2}
+= a^{(q-1)/2}\, b^{(q-1)/2}$.
+\end{proof}
+
+\subsubsection{} Le calcul du caractère quadratique peut se faire
+efficacement par un algorithme d'exponentiation rapide : ceci permet
+donc de savoir effectivement si un élément donné de $\FF_q^\times$
+admet une racine carrée.  (On renvoie à \refext{Fin}{remarques-critere-rabin}
+pour la question de la représentation des corps finis et
+l'algorithmique dans ceux-ci ; mais pour beaucoup de questions
+algorithmiques considérées ici, le cas où $q = p$ est premier et
+$\FF_q = \ZZ/p\ZZ$ est déjà intéressant.)  Calculer effectivement la
+racine carrée d'un élément qui en admet une est une question plus
+délicate.  Commençons par considérer le cas facile où $q \equiv
+3 \pmod{4}$ :
+
+\begin{lemme2}\label{carres-extensions-corps-finis}
+Soit $q = p^r$ avec $p$ premier impair.  Si $r$ est impair, alors un
+élément de $\FF_p$ est un carré dans $\FF_p$ si et seulement si il
+l'est dans $\FF_q$ (autrement dit, $\FF_q^{\times 2} \cap \FF_p
+= \FF_p^{\times 2}$).  Si $r$ est pair, alors tout élément de $\FF_p$
+est un carré dans $\FF_q$.
+\end{lemme2}
+\begin{proof}
+On peut par exemple, pour $a \in \FF_p^\times$, écrire $a^{(q-1)/2} =
+a^{(p^r-1)/2} = (a^{(p-1)/2})^{p^{r-1} + \cdots + p + 1}$, et
+$a^{(p-1)/2}$ vaut $+1$ ou $-1$ selon que $a$ est un carré
+dans $\FF_p$, et la parité de $p^{r-1} + \cdots + p + 1$ est la même
+que celle de $r$, ce qui démontre le résultat.
+
+Une autre démonstration consiste à considérer le polynôme $X^2 - a$ et
+à lui
+appliquer \refext{Fin}{corollaire-scindage-partiel-polynomes-corps-finis}.
+\end{proof}
+
+Mentionnons par ailleurs le résultat combinatoire suivant, qui est une
+application inattendue des propriétés du caractère quadratique sur les
+corps finis :
+\begin{proposition2}\label{matrice-d-hadamard-par-corps-finis}
+Soit $q$ une puissance d'un nombre premier vérifiant $q \equiv
+3 \pmod{4}$.  Alors il existe une matrice $M$ de taille $(q+1)\times
+(q+1)$ à coefficients dans $\{\pm 1\}$ telle que deux lignes
+distinctes quelconques de $M$ ont la même valeur en $\frac{1}{2}(q+1)$
+de leurs entrées et une valeur opposée en les $\frac{1}{2}(q+1)$
+autres.
+\end{proposition2}
+\begin{proof}
+En notant $\PP^1(\FF_q) = \FF_q \cup \{\infty\}$, on définit une
+fonction $\varphi\colon \PP^1(\FF_q) \times \PP^1(\FF_q) \to \{\pm
+1\}$ par $\varphi(\infty,\infty) = \varphi(x,\infty)
+= \varphi(\infty,y) = +1$ si $x \in \FF_q$ et $y \in \FF_q$, par
+$\varphi(x,x) = -1$ pour tout $x \in \FF_q$, et par $\varphi(x,y) =
+(x-y)^{(q-1)/2}$ (c'est-à-dire $+1$ ou $-1$ selon que $x-y$ est un
+carré ou non dans $\FF_q$, cf. \ref{denombrement-carres-f-q}) si
+$x\neq y$ avec $x,y\in \FF_q$.  La matrice indicée par
+$\PP^1(\FF_q) \times \PP^1(\FF_q)$ dont les coefficients sont donnés
+par la fonction $\varphi$ répond à la question : pour le montrer, il
+s'agit de voir que si $x,x' \in \PP^1(\FF_q)$ avec $x\neq x'$ alors il
+existe $\frac{1}{2}(q+1)$ valeurs $y \in \PP^1(\FF_q)$ exactement
+telles que $\varphi(x,y) = \varphi(x',y)$.
+
+Si $x$ vaut $\infty$, il s'agit de voir que $\frac{1}{2}(q+1)$ valeurs
+$y$ vérifient $\varphi(x',y) = -1$, c'est-à-dire (puisque
+$\varphi(x',x')=-1$) que $\frac{1}{2}(q-1)$ éléments $y \in \FF_q$
+sont tels que $x'-y$ ne soit pas un carré dans $\FF_q$, ce qui est
+bien le cas (cf. \ref{denombrement-carres-f-q}).  Si $x,x' \in \FF_q$,
+on s'intéresse à $\varphi(x,y)/\varphi(x',y)$.  Si $y \in \FF_q$ et
+$y \not\in \{x,x'\}$, cette fonction vaut
+$(\frac{x-y}{x'-y})^{(q-1)/2}$, or l'expression $\frac{x-y}{x'-y}$
+prend toutes les valeurs de $\FF_q$ sauf $0$ et $1$, donc
+$(\frac{x-y}{x'-y})^{(q-1)/2}$ prend $\frac{1}{2}(q-3)$ fois la
+valeur $+1$ ; si $y = \infty$, l'expression
+$\varphi(x,y)/\varphi(x',y)$ vaut $+1$ ; si $y=x$ ou $y=x'$, enfin,
+l'expression $\varphi(x,y)/\varphi(x',y)$ vaut $-(x'-x)^{(q-1)/2}$ et
+$-(x-x')^{(q-1)/2}$ respectivement, et ces valeurs sont opposées
+puisque $q\equiv 3 \pmod{4}$ entraîne $(-1)^{(q-1)/2} = -1$ ; on a
+donc montré que $\varphi(x,y)/\varphi(x',y)$ prend exactement
+$\frac{1}{2}(q+1)$ fois la valeur $+1$ lorsque $y$
+parcourt $\PP^1(\FF_q)$.
+\end{proof}
+
+Une matrice telle que fournie par la
+proposition \ref{matrice-d-hadamard-par-corps-finis}
+s'appelle \emph{matrice d'Hadamard} de taille $q+1$.  On conjecture
+qu'il existe une matrice d'Hadamard de toute taille multiple de $4$.
+
+\subsection{Algorithmes de calcul des racines carrées}
+
+\begin{proposition2}\label{tonelli-shanks-pour-3-mod-4}
+Soit $q$ une puissance d'un nombre premier impair.  On suppose
+$q \equiv 3 \pmod{4}$.  Alors :
+\begin{itemize}
+\item L'élément $-1 \in \FF_q^\times$ n'est pas un carré.
+\item Pour tout $D \in \FF_q^{\times2}$, une racine carrée de $D$ est
+donnée par $D^{(q+1)/4}$.  Si $D \in \FF_q^\times$ n'est pas un carré,
+la même expression produit une racine carrée de $-D$.
+\end{itemize}
+\end{proposition2}
+\begin{proof}
+Pour ce qui est de la première affirmation, on a $(-1)^{(q-1)/2} = -1$
+car $\frac{1}{2}(q-1)$ est impair (puisque $q-1 \equiv 2 \pmod{4}$).
+
+Pour ce qui est de la seconde, soit $z = D^{(q+1)/4}$ : on a alors
+$z^2 = D^{(q+1)/2} = D^q D^{-(q-1)/2} = \pm D$ où le signe est $+$ si
+$D^{(q-1)/2}=+1$, c'est-à-dire lorsque $D$ est un carré, et $-$ sinon.
+\end{proof}
+
+\begin{proposition2}\label{tonelli-shanks-pour-5-mod-8}
+Soit $q$ une puissance d'un nombre premier impair.  On suppose
+$q \equiv 5 \pmod{8}$.  Alors :
+\begin{itemize}
+\item L'élément $2 \in \FF_q^\times$ n'est pas un carré.
+\item Pour tout $D \in \FF_q^{\times2}$, une racine carrée de $D$ est
+donnée par $D^{(q+3)/8}$ ou par $2^{(q-1)/4}\,D^{(q+3)/8}$ selon que
+$D^{(q-1)/4}$ vaut $+1$ ou $-1$.
+\end{itemize}
+\end{proposition2}
+\begin{proof}
+Montrons d'abord que $2$ n'est pas un carré dans $\FF_q$.  Pour cela,
+écrivons $q = p^r$ avec $p$ premier : comme $q \equiv 5 \pmod{8}$ et
+que tous les carrés sont congrus à $1$ modulo $8$, on voit que $r$ est
+impair et $p \equiv 5 \pmod{8}$.  D'après le
+lemme \ref{carres-extensions-corps-finis}, il s'agit de montrer que
+$2$ n'est pas un carré dans $\FF_p = \ZZ/p\ZZ$.  Pour cela,
+considérons d'une part les $\frac{1}{2}(p-1)$ entiers
+$1,2,3,\ldots,\frac{p-1}{2}$, dont le produit est $(\frac{p-1}{2})!$,
+et considérons d'autre part leurs doubles, qui sont congrus modulo $p$
+à $2,4,6,\ldots,\frac{p-1}{2},\penalty-100
+-\frac{p-3}{2},-\frac{p-5}{2},\ldots,-1$ (on a choisi systématiquement
+le représentant de plus petite valeur absolue) ; or $\frac{p-1}{4}$
+(un nombre impair) parmi ces représentants sont négatifs et leurs
+valeurs absolues comptent bien chacun des entiers entre $1$ et
+$\frac{p-1}{2}$ : donc le produit des entiers
+$2,4,6,\ldots,\frac{p-1}{2},\penalty-100
+-\frac{p-3}{2},-\frac{p-5}{2},\ldots,-1$ est $-(\frac{p-1}{2})!$ ;
+mais ce produit est congru modulo $p$ à $2^{(p-1)/2}\,
+(\frac{p-1}{2})!$ puisqu'il s'agit des représentants des doubles des
+entiers $1,2,3,\ldots,\frac{p-1}{2}$.  On a donc prouvé que
+$2^{(p-1)/2} \equiv -1 \pmod{p}$, donc que $2$ n'est pas un carré
+modulo $p$, ni dans $\FF_q$.
+
+Passons à la seconde affirmation.  Soit $x = D^{(q+3)/8}$ : on a alors
+$x^2 = D^{(q+3)/4} = D \cdot D^{(q-1)/4}$.  Notons que $D^{(q-1)/4}$
+ne peut valoir que $+1$ ou $-1$ puisque son carré est $D^{(q-1)/2} =
+1$ (car $D$ est un carré).  Si $D^{(q-1)/4} = 1$, on a bien $x^2 = D$
+comme annoncé.  Si $D^{(q-1)/4} = -1$, on a $x^2 = -D$ : soit $x' =
+2^{(q-1)/4}\, x$ : on a $x^{\prime2} = 2^{(q-1)/2}\, x^2 = -x^2 = D$
+puisqu'on a démontré que $2^{(q-1)/2} = -1$.
+\end{proof}
+
+L'affirmation que $2$ n'est pas un carré dans $\FF_q$ lorsque
+$q \equiv 5 \pmod{8}$ sera généralisée ultérieurement (on verra
+en \ref{formule-complementaire} que
+$2^{(q-1)/2} = (-1)^{(q^2-1)/8}$ dans $\FF_q$, ce qui peut se montrer
+avec la même technique qu'on a utilisée ci-dessus).
+
+Les techniques de calcul de racines carrées explicitées dans les
+propositions \ref{tonelli-shanks-pour-3-mod-4} et \ref{tonelli-shanks-pour-5-mod-8}
+sont des cas particuliers d'un algorithme plus général appelé
+algorithme de Tonelli-Shanks.  Celui-ci est, cependant, d'autant plus
+malcommode que $q$ est congru à $1$ modulo une grande puissance
+de $2$, et par ailleurs on ne dispose plus d'un élément non carré
+aussi évident que $-1$ ou $2$ dans les deux cas étudiés ci-dessus.  Il
+vaut donc mieux utiliser d'autres algorithmes de factorisation, comme
+ceux de Cipolla ou de Legendre que nous allons présenter maintenant.
+
+\begin{proposition2}\label{proposition-algorithme-cipolla}
+Soit $q$ une puissance d'un nombre premier impair, et soit
+$D \in \FF_q^{\times2}$.  Si $u \in \FF_q$ est un élément quelconque
+tel que $(u^2-4D)^{(q-1)/2} = -1$, alors dans $\FF_q[X]/(X^2-uX+D)$ la
+classe $x$ de $X$ vérifie $x^{q+1} = D$, et $x^{(q+1)/2}$ est une
+racine carrée de $D$ dans $\FF_q$.
+\end{proposition2}
+\begin{proof}
+L'hypothèse $(u^2-4D)^{(q-1)/2} = -1$, c'est-à-dire que $u^2-4D$ n'est
+pas un carré dans $\FF_q$, implique que le polynôme $X^2 - uX + D$,
+dont le discriminant est $u^2 - 4D$, n'est pas scindé sur $\FF_q$,
+donc est irréductible, donc $\FF' = \FF_q[X]/(X^2-uX+D)$ est un corps,
+isomorphe à $\FF_{q^2}$.  L'élément $x$ représenté par $X$
+(c'est-à-dire, la multiplication par $x$ vue comme application
+$\FF_q$-linéaire sur $\FF'$) a pour polynôme minimal $X^2 - uX + D$
+(sur $\FF_q$) dont $x$ est une des deux racines (son conjugué étant
+$x^q = u-x$).  La norme $\N_{\FF'\bo\FF_q}(x)$ de $x$ sur $\FF_q$ vaut
+$x^{q+1} = D$ (cf. \refext{Fin}{trace-et-norme-corps-finis}).  Enfin,
+$x^{(q+1)/2}$, étant une racine carrée de $D$ dans le corps $\FF'$,
+doit être une des deux racines que cet élément a déjà dans $\FF_q$.
+\end{proof}
+
+\subsubsection{}\label{algorithme-cipolla} La proposition \ref{proposition-algorithme-cipolla}
+conduit à l'\emph{algorithme} suivant, dit de Cipolla, permettant de
+calculer une racine carrée de $D$ dans $\FF_q$ : dans un premier
+temps, choisir un $u$ tel que $u^2 - 4D$ ne soit pas un carré
+dans $\FF_q$ (ce qui se fait simplement en choisissant $u$ au hasard
+et en testant $(u^2-4D)^{(q-1)/2} = -1$ jusqu'à ce que cette condition
+soit vérifiée : on aura en moyenne environ $2$ essais à faire) ; puis,
+calculer $x^{(q+1)/2}$ dans $\FF' = \FF_q[X]/(X^2-uX+D)$
+(c'est-à-dire, calculer le reste de la division euclidienne de
+$X^{(q+1)/2}$ par $X^2-uX+D$) par un algorithme d'exponentiation
+rapide dans ce corps $\FF'$.  À ce sujet, les éléments de $\FF'$ se
+représentent par des couples $(c_0,c_1)$ d'éléments de $\FF_q$ (censés
+représenter $c_0 + c_1 x$), et les deux formules nécessaires pour
+appliquer une méthode d'exponentiation rapide, à savoir l'élévation au
+carré et la multipliation par $x$, sont représentées par les deux
+applications
+\[
+(c_0,c_1) \mapsto (c_0^2-Dc_1^2,\; 2 c_0 c_1 + uc_1^2)
+\]
+et
+\[
+(c_0,c_1) \mapsto (-D c_1,\; c_0 + u c_1)
+\]
+L'algorithme de Cipolla consiste donc à partir de $(0,1)$ et à
+appliquer tour à tour la première de ces fonctions puis éventuellement
+la seconde lorsque le chiffre correspondant de l'écriture binaire de
+$\frac{q+1}{2}$ (en partant du deuxième plus significatif, et en
+lisant vers le moins significatif) vaut $1$, jusqu'à avoir lu tous les
+chiffres.  Le résultat doit être de la forme $(d,0)$ où $d$ est une
+racine carrée comme recherchée.
+
+\begin{remarque2}
+Dans la situation ci-dessus ($q$ puissance d'un nombre premier impair,
+et $D$ carré dans $\FF_q$), on vient de remarquer que, si
+$(u^2-4D)^{(q-1)/2} = -1$, alors le reste de la division euclidienne
+de $X^{(q+1)/2}$ par $X^2-uX+D$ dans $\FF_q[X]$ vaut $\pm d$ où $d$
+est une racine carrée de $D$.  On peut se demander ce qui se produit
+si on applique l'algorithme de Cipolla sans avoir vérifié que
+$(u^2-4D)^{(q-1)/2} = -1$.  Lorsque $(u^2-4D)^{(q-1)/2} = +1$, alors
+le reste de $X^{(q+1)/2}$ par $X^2-uX+D$ vaut $\pm X$ : en effet,
+l'hypothèse $(u^2-4D)^{(q-1)/2} = +1$ assure que le polynôme
+$X^2-uX+D$ se factorise sur $\FF_q$ en $(X-a)(X-a')$ pour $a,a'$ deux
+éléments de $\FF_q$ (de somme $u$ et de produit $D$) ; alors le
+théorème chinois assure que $\FF_q[X]/(X^2-uX+D)$ est isomorphe à un
+produit $\FF_q \times \FF_q$ en envoyant la classe $x$ de $X$ sur $a$
+dans le premier facteur et $a'$ dans le second : par conséquent
+$x^{(q-1)/2}$ vaut $\pm 1$ (à savoir $+1$ si $a$ et $a'$ sont tous
+deux des carrés --- ils doivent l'être ensemble puisque leur produit
+est un carré --- et $-1$ si $a$ et $a'$ ne sont pas des carrés), et
+$x^{(q+1)/2}$ vaut alors $\pm x$.  Reste enfin le cas où
+$(u^2-4D)^{(q-1)/2} = 0$, c'est-à-dire $u = 2d$ avec $d$ une racine
+carrée de $D$ : alors $X^2-uX+D = (X-d)^2$ ; la valeur de
+$X^{(q+1)/2}$ en $X=d$ est $d^{(q+1)/2} = \pm d$ (le signe $\pm$ étant
+donné par $d^{(q-1)/2}$) et la dérivée de $X^{(q+1)/2}$ en $X=d$ est
+$\pm\frac{q+1}{2}$ : donc le reste de la division euclidienne de
+$X^{(q+1)/2}$ par $(X-d)^2$ vaut $\pm(\frac{q+1}{2}(X-d)+d)
+= \pm\frac{q+1}{2}(X+d)$.
+\end{remarque2}
+
+\begin{proposition2}\label{proposition-algorithme-legendre}
+Soit $q$ une puissance d'un nombre premier impair, et soit
+$D \in \FF_q^{\times2}$.  Si $y = a_0 + a_1 x$ (avec
+$a_0,a_1 \in \FF_q$) est un élément quelconque de $\FF_q[X]/(X^2-D)$
+(où on note $x$ la classe de $X$) et qu'on pose $t = y^{(q-1)/2}$
+(dans $\FF_q[X]/(X^2-D)$), noté $t = c_0 + c_1 x$ (avec
+$c_0,c_1 \in \FF_q$), alors une et une seule des affirmations
+suivantes est vraie :
+\begin{itemize}
+\item on a $y=0$ (soit $a_0=a_1=0$),
+\item on a $a_1 \neq 0$ et $a_0/a_1$ est une racine carrée de $D$
+dans $\FF_q$,
+\item on a $t=\pm 1$ (soit $c_1=0$ et $c_0=\pm 1$),
+\item on a $c_0=0$ et $c_1 \neq 0$, et $1/c_1$ est une racine carrée
+de $D$ dans $\FF_q$.
+\end{itemize}
+De plus, les nombres de $y \in \FF_q[X]/(X^2-D)$ vérifiant chacune de
+ces quatre affirmations valent respectivement : $1$, $2(q-1)$,
+$\frac{1}{2}(q-1)^2$ et $\frac{1}{2}(q-1)^2$.
+\end{proposition2}
+\begin{proof}
+Soient $d$ et $-d$ les deux racines carrées de $D$ dans $\FF_q$.  Le
+théorème chinois assure que $\FF_q[X]/(X^2-D)$ est isomorphe à un
+produit $\FF_q \times \FF_q$ en envoyant la classe $x$ de $X$ sur $d$
+dans le premier facteur et $-d$ dans le second (soit l'isomorphisme
+$a_0 + a_1 x \mapsto (a_0+a_1 d, a_0-a_1 d)$).  Remarquons que $y =
+a_0 + a_1 x$ est nul dans le second facteur $\FF_q$ si et seulement si
+$a_0 - a_1 d = 0$, c'est-à-dire $a_1 = 0$ ou bien $d = a_0/a_1$, et
+nul dans le premier facteur si et seulement si $a_1 = 0$ ou bien $d =
+-a_0/a_1$.  On a ainsi réparti les $q^2$ éléments de
+$\FF_q[X]/(X^2-D)$ en $1$ élément nul, $2(q-1)$ éléments $a_0 + a_1 x$
+tels que $a_1 \neq 0$ mais que $a_0/a_1$ soit une racine carrée de $D$
+(il y en a $q-1$ pour lesquels c'est $d$ et $q-1$ pour lesquels
+c'est $-d$) et $(q-1)^2$ éléments non nuls dans chacun des deux
+facteurs chinois (i.e., $a_0+a_1 d \neq 0$ et $a_0-a_1 d \neq 0$).  On
+se place à présent dans ce dernier cas.
+
+Pour tout élément non nul $z$ de $\FF_q$ on a $z^{(q-1)/2} = \pm 1$,
+ce nombre valant $+1$ pour $\frac{1}{2}(q-1)$ éléments $z$, et $-1$
+pour les $\frac{1}{2}(q-1)$ autres
+(cf. \ref{denombrement-carres-f-q}).  On en déduit que si $t =
+y^{(q-1)/2}$ s'écrit $t = c_0 + c_1 x$, alors chacun des éléments $c_0
++ c_1 d = (a_0 + a_1 d)^{(q-1)/2}$ et $c_0 - c_1 d = (a_0 - a_1
+d)^{(q-1)/2}$ vaut $+1$ ou $-1$.  Et chacune des quatre combinaisons
+de signes est réalisée pour $[\frac{1}{2}(q-1)]^2$ éléments (parmi les
+$(q-1)^2$ considérés) de $\FF_q[X]/(X^2-D) \cong \FF_q \times \FF_q$.
+Lorsque $c_0 + c_1 d$ et $c_0 - c_1 d$ sont égaux, ce qui se produit
+dans $\frac{1}{2}(q-1)^2$ cas, on a ainsi $c_1 = 0$ et $c_0 = t = \pm
+1$.  Lorsque $c_0 + c_1 d$ et $c_0 - c_1 d$ sont opposés, ce qui se
+produit également dans $\frac{1}{2}(q-1)^2$ cas, on a ainsi $c_0 = 0$
+et $c_1 d = \pm 1$, de sorte que $1/c_1 = \pm d$ est une racine carrée
+de $D$.
+\end{proof}
+
+\subsubsection{}\label{algorithme-legendre} La proposition \ref{proposition-algorithme-legendre}
+conduit à l'\emph{algorithme} suivant, dit de Legendre, permettant de
+calculer une racine carrée de $D$ dans $\FF_q$ : dans un premier
+temps, tirer $y = a_0 + a_1 x$ aléatoirement dans $\FF_q[X]/(X^2-D)$
+(on peut se limiter à $a_1 \neq 0$, puisque le cas où $y \in \FF_q$
+n'est pas susceptible de produire un résultat intéressant).  Puis
+calculer $t = y^{(q-1)/2}$ dans $\FF_q[X]/(X^2-D)$ (c'est-à-dire,
+calculer le reste de la division euclidienne de $X^{(q-1)/2}$ par
+$X^2-D$) par un algorithme d'exponentiation rapide dans cet
+anneau $\FF_q[X]/(X^2-D)$.  Si le résultat $c_0 + c_1 x$ est de la
+forme $c_1 = 0$ (auquel cas $c_0 = \pm 1$), on doit choisir un
+nouveau $y$ et recommencer, tandis que si $c_0 + c_1 x$ est de la
+forme $c_0 = 0$ alors $1/c_1$ fournit la racine carrée recherchée ;
+quant au petit nombre (du moins si $q$ est grand) de $y$ dans le
+second cas de \ref{proposition-algorithme-legendre-caracteristique-2},
+on peut soit les écarter \emph{a priori} en vérifiant
+avant de commencer si $a_0/a_1$ est une racine carrée de $D$, soit
+plus vraisemblablement les traiter \emph{a posteriori} en renvoyant
+$a_0/a_1$ comme racine carrée (ou d'ailleurs $c_0/c_1$, qui lui est
+égal) si l'on obtient simultanément $c_0 \neq 0$ et $c_1 \neq 0$ (le
+nombre $t$, comme $y$, est nul dans un des facteurs chinois et pas
+dans l'autre).
+
+De même que pour l'algorithme de
+Cipolla (cf. \ref{algorithme-cipolla}), les éléments de
+$\FF_q[X]/(X^2-D)$ se représentent par des couples $(c_0,c_1)$
+d'éléments de $\FF_q$ (censés représenter $c_0 + c_1 x$), et les deux
+formules nécessaires pour appliquer une méthode d'exponentiation
+rapide, à savoir l'élévation au carré et la multipliation par $y = a_0
++ a_1 x$, sont représentées par les deux applications
+\[
+(c_0,c_1) \mapsto (c_0^2+Dc_1^2,\; 2 c_0 c_1)
+\]
+et
+\[
+(c_0,c_1) \mapsto (a_0 c_0 + D a_1 c_1,\; a_0 c_1 + a_1 c_0)
+\]
+L'algorithme de Legendre consiste donc à partir d'un $(c_0,c_1) =
+(a_0,a_1)$ tiré au hasard (avec $a_1 \neq 0$) et à appliquer tour à
+tour la première de ces fonctions puis éventuellement la seconde selon
+ce que vaut le chiffre correspondant de l'écriture binaire de
+$\frac{q-1}{2}$.  On procède alors comme expliqué ci-dessus.
+
+\begin{remarque2}
+Si $q \equiv 3 \pmod{4}$ (de sorte que $-1$ n'est pas un carré
+dans $\FF_q$ d'après \ref{tonelli-shanks-pour-3-mod-4}), alors on peut
+choisir $u=0$ dans l'algorithme de Cipolla \ref{algorithme-cipolla}
+comme on peut choisir $y = x$ dans l'algorithme de
+Legendre \ref{algorithme-legendre} : on se convainc alors facilement
+que calculer le premier (calculer $x^{(q+1)/2}$ dans
+$\FF_q[X]/(X^2+D)$) revient à calculer $(-D)^{(q+1)/4} = \pm
+D^{(q+1)/4}$, tandis que le second (calculer $x^{(q-1)/2}$ dans
+$\FF_q[X]/(X^2+D)$) donne $D^{(q-3)/4} x$, de sorte que la racine
+carrée calculée est $D^{(q+1)/4}$.  Ainsi, dans le cas $q \equiv
+3 \pmod{4}$, la méthode de calcul de racine carrée exposée
+en \ref{tonelli-shanks-pour-3-mod-4} peut se voir aussi bien comme un
+cas particulier de l'algorithme de Cipolla que de celui de Legendre.
+\end{remarque2}
+
+\subsection{La caractéristique $2$}\label{equations-quadratiques-corps-finis-caracteristique-2}
+
+\subsubsection{} En caractéristique $2$, calculer
+des racines carrées dans $\FF_q = \FF_{2^r}$ est facile : on a
+$x^{2^r} = x$ d'après \refext{Fin}{petit-theoreme-fermat}, donc $x^{2^{r-1}}$
+est une racine carrée de $x$.  À la différence du cas où $2$ est
+inversible, cependant, savoir calculer des racines carrées ne permet
+pas de résoudre toutes les équations quadratiques puisqu'on ne peut
+pas écrire $X^2 + bX + c = 0$ sous la forme $(X+\frac{b}{2})^2 +
+(c-\frac{b^2}{4}) = 0$.  À la place, si on note $\wp(Z) = Z^2 + Z$,
+l'équation $X^2 + bX + c = 0$, lorsque $b\neq 0$ (le cas $b=0$ ayant
+déjà été traité) peut se réécrire $\wp(X/b)+(c/b^2) = 0$, soit $X =
+b\,\root\wp\of{c/b^2}$ si on note $\root\wp\of E$ une solution (si
+elle existe) de l'équation $Z^2+Z = E$, l'autre solution étant alors
+$\root\wp\of E + 1$ (puisque $\wp(Z+1) = \wp(Z)$).
+
+\begin{definition2}
+Soit $q = 2^r$ une puissance de $2$.  On appelle \emph{caractère
+quadratique additif} sur $\FF_q$ la fonction $\tau \colon a \mapsto a
++ a^2 + a^4 + a^8 + \cdots + a^{2^{r-1}}$ (qu'on notera aussi $\tau_r$
+en cas d'ambiguïté).  On note $\wp\FF_q$ l'ensemble des éléments de
+$\FF_q$ qui sont dans l'image de la fonction $\wp\colon z \mapsto z^2
++ z$.
+\end{definition2}
+
+On peut aussi considérer $\tau$ comme la trace pour l'extension
+$\FF_q\bo\FF_2$ (cf. \refext{Fin}{trace-et-norme-corps-finis}).
+
+\begin{proposition2}\label{denombrement-artin-schreier-2-f-q}
+Si $q$ est une puissance de $2$, alors le caractère quadratique
+additif $\tau$ ne prend sur $\FF_q$ que les valeurs $0$ et $1$, et on
+a $a \in \wp\FF_q$ si et seulement si $\tau(a) = 0$ ; de plus,
+$\#(\wp\FF_q) = \frac{q}{2}$.
+\end{proposition2}
+\begin{proof}
+L'application $\wp\colon z \mapsto z^2+z$, vue comme une application
+$\FF_2$-linéaire $\FF_q \to \FF_q$, a pour noyau $\{0,1\}$ (de
+cardinal $2$) puisque $0,1$ sont les deux solutions de $Z^2 + Z = 0$ ;
+et elle a pour image $\wp\FF_q$, donc $2\, \#(\wp\FF_q) = \#\FF_q$ :
+ceci montre la dernière affirmation.
+
+Si $e = \tau(a)$ avec $a \in \FF_q$, alors $\wp(e) = e^2 + e = (a^2 +
+a^4 + \cdots + a^q) + (a + a^2 + \cdots + a^{q/2}) = 0$ puisque $a^{q}
+= a$, donc $e$ vaut $0$ ou $1$.
+
+Si $a = \wp(b)$ avec $b \in \FF_q$, alors $\tau(a) = a + a^2 + \cdots
++ a^{q/2} = (b^2 + b) + (b^4 + b^2) + \cdots + (b^{q} + b^{q/2}) = 0$.
+On a donc montré que sur tout élément de $\wp\FF_q$ le caractère
+quadratique additif $\tau$ vaut $0$ : comme on vient de voir qu'il y a
+$\frac{q}{2}$ tels éléments et que le polynôme $X + X^2 + X^4 + \cdots
++ X^{q/2}$ (de degré $\frac{q}{2}$) n'est pas nul, il ne peut
+s'annuler en aucun autre point de $\FF_q$ : on voit donc que
+réciproquement si $\tau(a) = 0$ alors $a \in \wp\FF_q$.
+\end{proof}
+
+La proposition suivante est l'analogue
+de \ref{proposition-algorithme-cipolla} pour la caractéristique $2$ :
+\begin{proposition2}\label{proposition-algorithme-cipolla-caracteristique-2}
+Soit $q = 2^r$ une puissance de $2$, et soit $E \in \wp\FF_q$.  Si
+$v \in \FF_q$ est un élément quelconque tel que $\tau(v/E^2) = 1$,
+alors dans $\FF_q[X]/(X^2+EX+v)$ la classe $x$ de $X$ vérifie $x^q + x
+= E$, et $x + x^2 + x^4 + x^8 + \cdots + x^{q/2}$ est une racine
+de $Z^2+Z+E=0$ dans $\FF_q$.
+\end{proposition2}
+\begin{proof}
+L'hypothèse $\tau(v/E^2) = 1$, c'est-à-dire que $v/E^2$ n'est pas
+dans $\wp\FF_q$ (cf. \ref{denombrement-artin-schreier-2-f-q}),
+implique que le polynôme $X^2 + EX + v$ n'est pas scindé sur $\FF_q$,
+donc est irréductible, donc $\FF' = \FF_q[X]/(X^2+EX+v)$ est un corps,
+isomorphe à $\FF_{q^2}$.  L'élément $x$ représenté par $X$
+(c'est-à-dire, la multiplication par $x$ vue comme application
+$\FF_q$-linéaire sur $\FF'$) a pour polynôme minimal $X^2 + EX + v$
+(sur $\FF_q$) dont $x$ est une des deux racines (son conjugué étant
+$x^q = x + E$).  La trace $\Tr_{\FF'\bo\FF_q}(x)$ de $x$ sur $\FF_q$
+vaut $x^q + x = E$ (cf. \refext{Fin}{trace-et-norme-corps-finis}).  Enfin, on
+a $(x + x^2 + x^4 + \cdots + x^{q/2})^2 + \penalty-500 (x + x^2 + x^4
++ \cdots + x^{q/2}) =\penalty-500 (x^2 + x^4 + x^8 + \cdots + x^q) +
+(x + x^2 + x^4 + \cdots + x^{q/2}) = x^q + x = E$ ; ainsi, la quantité
+$y = x + x^2 + x^4 + \cdots + x^{q/2}$, étant une racine de $Z^2 + Z +
+E = 0$ dans le corps $\FF'$, doit être une des deux racines que cette
+équation a déjà dans $\FF_q$.
+\end{proof}
+
+La proposition suivante est l'analogue
+de \ref{proposition-algorithme-legendre} pour la caractéristique $2$ :
+\begin{proposition2}\label{proposition-algorithme-legendre-caracteristique-2}
+Soit $q = 2^r$ une puissance de $2$, et soit $E \in \wp\FF_q$.  Si $y
+= a_0 + a_1 x$ (avec $a_0,a_1 \in \FF_q$) est un élément quelconque de
+$\FF_q[X]/(X^2+X+E)$ (où on note $x$ la classe de $X$) et qu'on pose
+$t = y + y^2 + y^4 + \cdots + y^{q/2}$ (dans $\FF_q[X]/(X^2+X+E)$),
+noté $t = c_0 + c_1 x$ (avec $c_0,c_1 \in \FF_q$), alors une et une
+seule des affirmations suivantes est vraie :
+\begin{itemize}
+\item on a $t \in \{0,1\}$ (soit $c_1=0$ et $c_0 \in \{0,1\}$),
+\item on a $c_1=1$, et $c_0$ est une racine
+de $Z^2 + Z + E = 0$ dans $\FF_q$.
+\end{itemize}
+De plus, les nombres de $y \in \FF_q[X]/(X^2+X+E)$ vérifiant chacune de
+ces deux affirmations valent chacun $q^2/2$.
+\end{proposition2}
+\begin{proof}
+Soient $e$ et $e+1$ les deux racines de $Z^2 + Z + E = 0$
+dans $\FF_q$.  Le théorème chinois assure que $\FF_q[X]/(X^2+X+E)$ est
+isomorphe à un produit $\FF_q \times \FF_q$ en envoyant la classe $x$
+de $X$ sur $e$ dans le premier facteur et $e+1$ dans le second (soit
+l'isomorphisme $a_0 + a_1 x \mapsto (a_0+a_1 e, {(a_0+a_1)}+a_1 e)$).
+
+Pour tout élément non nul $z$ de $\FF_q$ on a $z + z^2 + z^4 + \cdots
++ z^{q/2} \in \{0, 1\}$, ce nombre valant $0$ pour $\frac{q}{2}$
+éléments $z$, et $1$ pour les $\frac{q}{2}$ autres
+(cf. \ref{denombrement-artin-schreier-2-f-q}).  On en déduit que si $t
+= y + y^2 + y^4 + \cdots + y^{q/2}$ s'écrit $t = c_0 + c_1 x$, alors
+chacun des éléments $c_0 + c_1 e = \tau(a_0 + a_1 e)$ et $(c_0+c_1) +
+c_1 e = \tau((a_0+a_1) + a_1 e)$ vaut $0$ ou $1$.  Et chacune des
+quatre combinaisons de valeurs est réalisée pour $(\frac{q}{2})^2$
+éléments de $\FF_q[X]/(X^2+X+E) \cong \FF_q \times \FF_q$.  Lorsque
+$c_0 + c_1 e$ et $(c_0+c_1) + c_1 e$ sont égaux, ce qui se produit
+dans $\frac{q^2}{2}$ cas, on a ainsi $c_1 = 0$ et $c_0 = t \in \{0,
+1\}$.  Lorsque $c_0 + c_1 e$ et $(c_0+c_1) + c_1 e$ diffèrent de $1$,
+ce qui se produit également dans $\frac{q^2}{2}$ cas, on a ainsi $c_1
+= 1$ et $c_0 + c_1 e \in \{0, 1\}$, de sorte que $c_0 \in \{e, e+1 \}$
+est une racine de $Z^2 + Z + E = 0$.
+\end{proof}
+
+\subsubsection{}\label{algorithmes-cipolla-legendre-caracteristique-2} On peut tirer des
+propositions \ref{proposition-algorithme-cipolla-caracteristique-2} et \ref{proposition-algorithme-legendre-caracteristique-2}
+des algorithmes, tout à fait analogues à ceux décrits
+en \ref{algorithme-cipolla} et \ref{algorithme-legendre}
+respectivement (et méritant sans doute de s'appeler également des noms
+de Cipolla et Legendre), permettant de résoudre des équations de la
+forme $Z^2 + Z + E = 0$ (et, compte tenu des remarques faites
+en \ref{equations-quadratiques-corps-finis-caracteristique-2}, toutes
+les équations quadratiques).
+
+S'agissant de l'algorithme de Cipolla, on trouve dans un premier temps
+un $v \neq 0$ tel que $v/E^2$ ne soit pas dans l'image de $\wp$, soit
+$\tau(v/E^2) = 1$ (ce qui se fait simplement en choisissant $v$ au
+hasard jusqu'à ce que cette condition soit vérifiée : on aura en
+moyenne $2$ essais à faire), puis on calcule $x + x^2 + \cdots +
+x^{q/2}$ dans $\FF' = \FF_q[X]/(X^2+EX+v)$.  Pour cela, on représente
+les éléments de $\FF'$ par des couples $(c_0,c_1)$ d'éléments
+de $\FF_q$ (censés représenter $c_0 + c_1 x$), et la formule
+nécessaire pour l'élévation au carré est représentée par l'application
+\[
+(c_0,c_1) \mapsto (c_0^2 + v c_1^2, E c_1^2)
+\]
+L'algorithme de Cipolla consiste en caractéristique $2$ donc à partir
+de $(0,1)$ et à appliquer $r-1$ fois l'application en question (si $q
+= 2^r$), puis à sommer les éléments en question.  Le résultat doit
+être de la forme $(e,0)$ où $e$ est une racine $\wp$-ième comme
+recherchée.
+
+S'agissant de l'algorithme de Legendre, on tire aléatoirement $y$ dans
+$\FF_q[X]/(X^2+X+E)$ et on calcule $t = y + y^2 + \cdots + y^{q/2}$ :
+si le résultat $c_0 + c_1 x$ est de la forme $c_1 = 0$ (auquel cas
+$c_0 \in \{0,1\}$), on doit choisir un nouveau $y$ et recommencer,
+sinon $c_1 = 1$ et $c_0$ est la racine recherchée.  De nouveau, on
+représente les éléments de $\FF_q[X]/(X^2+X+E)$ par des couples
+$(c_0,c_1)$ d'éléments de $\FF_q$, et l'élévation au carré est
+représentée par l'application
+\[
+(c_0,c_1) \mapsto (c_0^2 + E c_1^2, c_1^2)
+\]
+L'algorithme de Legendre en caractéristique $2$ consiste donc à partir
+d'un $(c_0,c_1) = (a_0,a_1)$ tiré au hasard et à appliquer $r-1$ fois
+l'application en question (si $q = 2^r$), puis à sommer les éléments
+en question.  On procède alors comme on vient d'expliquer.
+
+
+\section{Réciprocité quadratique}
+
+\subsection{Le symbole de Legendre}
+
+\begin{definition2}\label{definition-symbole-legendre}
+Si $p$ est un nombre premier impair et $a$ un entier, on
+appelle \emph{symbole de Legendre} de $a$ modulo $p$, et on note
+$\Legendre{a}{p}$, l'entier valant $0$ si $p|a$, et $1$ si $a$ est un
+carré dans $\FF_p$, et $-1$ si $a$ n'est pas un carré dans $\FF_p$.
+\end{definition2}
+
+Il résulte trivialement de \ref{denombrement-carres-f-q} et
+de \ref{produits-de-non-carres-dans-f-q} que :
+\begin{proposition2}\label{formule-symbole-legendre}
+Si $p$ est un nombre premier impair et $a$ un entier, alors
+\[
+\Legendre{a}{p} \equiv a^{(p-1)/2} \pmod{p}
+\]
+De plus, quels que soient les entiers $a,b$, on a $\Legendre{ab}{p}
+= \Legendre{a}{p} \Legendre{b}{p}$.
+\end{proposition2}
+
+\subsection{Réciprocité quadratique et formule complémentaire}
+
+L'énoncé suivant, qui compare le caractère quadratique de $p$ modulo
+$q$ au caractère quadratique de $q$ modulo $p$, et dont on va donner
+deux démonstrations, porte le nom de \emph{loi de réciprocité
+quadratique} :
+
+\begin{theoreme2}\label{loi-reciprocite-quadratique}
+Soient $p,q$ deux nombres premiers impairs distincts.  On a alors :
+\[
+\Legendre{p}{q} \Legendre{q}{p} = (-1)^{(p-1)(q-1)/4}
+\]
+--- c'est-à-dire $\Legendre{q}{p} = \Legendre{p}{q}$ sauf si
+$p,q \equiv 3 \pmod{4}$ auquel cas $\Legendre{q}{p} =
+-\Legendre{p}{q}$.
+\end{theoreme2}
+\begin{proof}[Première démonstration]
+Convenons pour cette démonstration de représenter les éléments de
+$\ZZ/p\ZZ$ par $-\frac{p-1}{2},\ldots,\frac{p-1}{2}$, et de
+dire d'un élément de $(\ZZ/p\ZZ)^\times$ qu'il est « positif »
+lorsqu'il est congru à l'un des $\frac{p-1}{2}$ entiers
+$1,2,3,\ldots,\frac{p-1}{2}$, et « négatif » lorsqu'il est congru à
+l'un des $\frac{p-1}{2}$ entiers $-\frac{p-1}{2},\ldots,-1$.  Avec
+cette définition, si $k \in \ZZ$ n'est pas multiple de $p$, son
+« signe » modulo $p$ (c'est-à-dire $+1$ ou $-1$ selon qu'il a un
+résidu positif ou négatif) vaut $(-1)^{\lfloor 2k/p\rfloor}$ où
+$\lfloor\tiret\rfloor$ désigne la fonction partie entière.  Remarquons
+d'ores et déjà que pour tout entier $i$ non multiple de $p$ on a
+$\lfloor \frac{2qi}{p}\rfloor + \lfloor \frac{q(p-2i)}{p}\rfloor =
+q-1$ (car $\lfloor\theta\rfloor +
+\lfloor q-\theta\rfloor = q-1$ pour tout
+$\theta \in \RR \setminus \ZZ$), et que cet entier est pair, de sorte
+que $(-1)^{\lfloor 2qi/p\rfloor} = (-1)^{\lfloor q(p-2i)/p\rfloor}$
+(ces deux expressions donnent donc le signe de $qi$ modulo $p$).
+
+Le produit $\prod_{i=1}^{(p-1)/2} \bar\imath$ des éléments positif de
+$(\ZZ/p\ZZ)^\times$ vaut $(\frac{p-1}{2})!$ modulo $p$.  Considérons
+maintenant le produit $\prod_{i=1}^{(p-1)/2} q\bar\imath$ : on peut
+manifestement l'écrire comme $q^{(p-1)/2} (\frac{p-1}{2})!$
+modulo $p$.  Mais par ailleurs on ne peut pas avoir $q\bar\imath =
+\pm q\bar\imath'$ pour $i,i' \in \{1,\ldots,\frac{p-1}{2}\}$ distincts,
+donc les $q\bar\imath$ s'écrivent $\pm\bar\jmath$ avec $\bar\jmath$
+parcourant $1,2,3,\ldots,\frac{p-1}{2}$ et le signe $\pm$ donné par
+$(-1)^{\lfloor 2qi/p\rfloor} = (-1)^{\lfloor q(p-2i)/p\rfloor}$ comme
+on l'a expliqué ; ainsi, $\prod_{i=1}^{(p-1)/2} q\bar\imath =
+(-1)^{\sum_{i=1}^{(p-1)/2} \lfloor 2qi/p\rfloor}(\frac{p-1}{2})!$, et
+en comparant les deux expressions trouvées et en
+utilisant \ref{formule-symbole-legendre}, on a $\Legendre{q}{p} =
+(-1)^{\sum_{i=1}^{(p-1)/2} \lfloor 2qi/p\rfloor}$ (« lemme
+d'Eisenstein »), ou, mieux, $\Legendre{q}{p} =
+(-1)^{\sum_{m=1}^{(p-1)/2} \lfloor qm/p\rfloor}$ (en appelant $m$ le
+nombre $2i$ ou $p-2i$ selon que $0<i<\frac{p}{4}$ ou
+$\frac{p}{4}<i<\frac{p}{2}$, de sorte que $m$ parcourt aussi les
+entiers de $1$ à $\frac{p-1}{2}$ quand $i$ les parcourt).
+
+Cette dernière expression admet l'interprétation géométrique
+suivante : $\Legendre{q}{p}$ vaut $(-1)^\mu$ avec $\mu$ le nombre de
+points $(m,n)$ à coordonnées entières telles que $0<m<\frac{p}{2}$ et
+$0<n<\frac{q}{p}m$ et (donc) $0<n<\frac{q}{2}$, ou, si l'on préfère,
+le nombre de points à coordonnées entières strictement à l'intérieur
+du triangle du plan dont les sommets sont $(0,0)$, $(\frac{p}{2},0)$
+et $(\frac{p}{2},\frac{q}{2})$.  On en déduit que
+$\Legendre{p}{q} \Legendre{q}{p}$ est $(-1)^{\mu+\nu}$ avec $\mu+\nu$
+le nombre de points $(m,n)$ à coordonnées entières vérifiant
+$0<m<\frac{p}{2}$ et $0<n<\frac{q}{2}$ : on a bien $\mu+\nu
+= \frac{(p-1)(q-1)}{4}$.
+\end{proof}
+\begin{proof}[Seconde démonstration]
+Considérons $\FF_{q^r} = \FF_q(\zeta)$ (où $r$ est l'ordre
+multiplicatif de $p$ modulo $q$) l'extension de $\FF_q$ par une racine
+primitive $p$-ième de l'unité $\zeta$, c'est-à-dire le corps de
+décomposition de $\Phi_p(X)$ sur $\FF_q$
+(cf. \refext{Fin}{factorisation-phi-n}) dont on note $\zeta$ une racine.  Dans
+ce corps, considérons la somme
+\[
+G = \sum_{i\in\FF_p^\times} \Legendre{i}{p} \zeta^i
+\]
+où on confond abusivement un $i \in \FF_p$ avec un représentant
+quelconque de celui-ci dans $\ZZ$ (puisque $\Legendre{i}{p}$ et
+$\zeta^i$ ne dépendent de la classe de $i$ modulo $p$).
+
+On a alors $G^2
+= \sum_{i,j\in \FF_p^\times} \Legendre{ij}{p} \zeta^{i+j}
+= \sum_{i,t \in \FF_p^\times} \Legendre{t}{p} \zeta^{i(1+t)}$ (en
+posant $t = j/i \in \FF_p^\times$ et en utilisant le fait que
+$\Legendre{i}{p}^2 = 1$) ; comme $\sum_{i\in\FF_p^\times} \zeta^{iu}$
+vaut $-1$ si $u \in \FF_p^\times$ et vaut $p - 1$ si $u = 0$, on en
+déduit (en distinguant selon que $t=-1$ ou non) $G^2
+= \Legendre{-1}{p}(p-1) - \sum_{t\neq 0,-1} \Legendre{t}{p}
+= \Legendre{-1}{p} p$ car $\sum_{t\in\FF_p^\times} \Legendre{t}{p} =
+0$ en vertu de \ref{denombrement-carres-f-q}.
+
+Par ailleurs, $G^q = \Frob_q(G)
+= \sum_{i\in\FF_p^\times} \Legendre{i}{p} \zeta^{qi}
+= \sum_{j\in\FF_p^\times} \Legendre{q}{p} \Legendre{j}{p} \zeta^j$ (en
+posant $j = qi$ et en utilisant de nouveau le fait que
+$\Legendre{q}{p}$ est son inverse), donc $G^q = \Legendre{q}{p} G$, et
+par conséquent $G^{q-1} = \Legendre{q}{p}$.
+
+En écrivant $G^{q-1} = (G^2)^{(q-1)/2}$, on a donc prouvé
+$\Legendre{q}{p} = \Legendre{-1}{p}^{(q-1)/2} p^{(q-1)/2} =
+(-1)^{(p-1)(q-1)/4} \Legendre{p}{q}$ ; cette égalité entre éléments de
+$\{\pm 1\}$ a lieu dans $\FF_{q^r}$ donc dans $\ZZ$ : c'est ce qu'on
+voulait prouver.
+\end{proof}
+
+Pour ce qui est du caractère quadratique de $2$, il est déterminé par
+la proposition suivante souvent appelée « formule complémentaire » :
+\begin{proposition2}\label{formule-complementaire}
+Soit $p$ un nombre premier impair.  On a alors :
+\[
+\Legendre{2}{p} = (-1)^{(p^2-1)/8}
+\]
+--- c'est-à-dire $\Legendre{2}{p} = 1$ si $p\equiv 1,7 \pmod{8}$ et
+$\Legendre{2}{p} = -1$ si $p\equiv 3,5 \pmod{8}$.
+\end{proposition2}
+\begin{proof}[Première démonstration]
+Convenons pour cette démonstration de représenter les éléments de
+$\ZZ/p\ZZ$ par $-\frac{p-1}{2},\ldots,\frac{p-1}{2}$, et de
+dire d'un élément de $(\ZZ/p\ZZ)^\times$ qu'il est « positif »
+lorsqu'il est congru à l'un des $\frac{p-1}{2}$ entiers
+$1,2,3,\ldots,\frac{p-1}{2}$, et « négatif » lorsqu'il est congru à
+l'un des $\frac{p-1}{2}$ entiers $-\frac{p-1}{2},\ldots,-1$.
+
+Le produit $\prod_{i=1}^{(p-1)/2} \bar\imath$ des éléments positif de
+$(\ZZ/p\ZZ)^\times$ vaut $(\frac{p-1}{2})!$ modulo $p$.  Considérons
+maintenant le produit $\prod_{i=1}^{(p-1)/2} 2\bar\imath$ : on peut
+manifestement l'écrire comme $2^{(p-1)/2} (\frac{p-1}{2})!$
+modulo $p$.  Mais par ailleurs on ne peut pas avoir $2\bar\imath =
+\pm 2\bar\imath'$ pour $i,i' \in \{1,\ldots,\frac{p-1}{2}\}$ distincts,
+donc les $2\bar\imath$ s'écrivent $\pm\bar\jmath$ avec $\bar\jmath$
+parcourant $1,2,3,\ldots,\frac{p-1}{2}$ et le signe $\pm$ (donné par
+$(-1)^{\lfloor 4i/p\rfloor}$ si l'on veut) vaut $+$ pour
+$0<i<\frac{p}{4}$ et $-$ pour $\frac{p}{4}<i<\frac{p}{2}$.  Le nombre
+de signes $-$ est donc égal au nombre d'entiers entre $\frac{p}{4}$ et
+$\frac{p}{2}$ et il est facile de se convaincre (par exemple en
+considérant séparément chaque cas $1,3,5,7$ modulo $8$) que le signe
+du produit est alors $(-1)^{(p^2-1)/8}$.  Ainsi,
+$\prod_{i=1}^{(p-1)/2} 2\bar\imath =
+(-1)^{(p^2-1)/8}(\frac{p-1}{2})!$, et en comparant les deux
+expressions trouvées et en utilisant \ref{formule-symbole-legendre},
+on a $\Legendre{2}{p} = (-1)^{(p^2-1)/8}$.
+
+(Cette démonstration a déjà été donnée, dans un cas particulier,
+en \ref{tonelli-shanks-pour-5-mod-8}.)
+\end{proof}
+\begin{proof}[Seconde démonstration]
+Considérons $\FF_{p^r} = \FF_p(\zeta)$ (où $r$ est l'ordre
+multiplicatif de $8$ modulo $p$) l'extension de $\FF_p$ par une racine
+primitive $8$-ième de l'unité $\zeta$, c'est-à-dire le corps de
+décomposition de $\Phi_8(X)$ sur $\FF_p$
+(cf. \refext{Fin}{factorisation-phi-n}) dont on note $\zeta$ une racine.  Dans
+ce corps, considérons la somme
+\[
+G = \zeta - \zeta^3 - \zeta^5 + \zeta^7
+\]
+
+On a alors $G^2 = 4 - 4\zeta^4 = 8$.
+
+Par ailleurs, $G^p = \Frob_p(G) = \zeta^p - \zeta^{3p} - \zeta^{5p}
++ \zeta^{7p}$, donc $G^p = (-1)^{(p^2-1)/8} G$ (en considérant
+séparément les cas $p\equiv 1,7\pmod{8}$ et $p\equiv 3,5\pmod{8}$), et
+par conséquent $G^{p-1} = (-1)^{(p^2-1)/8}$.
+
+En écrivant $G^{p-1} = (G^2)^{(p-1)/2}$, on a donc prouvé
+$(-1)^{(p^2-1)/8} = 8^{(p-1)/2} = \Legendre{8}{p} = \Legendre{2}{p}$ ;
+cette égalité entre éléments de $\{\pm 1\}$ a lieu dans $\FF_{p^r}$
+donc dans $\ZZ$ : c'est ce qu'on voulait prouver.
+\end{proof}
+
+\begin{remarque2}
+L'étude des nombres premiers $p$ pour lesquels $2$ est un \emph{cube}
+est plus délicate et s'insère naturellement dans la « théorie
+non abélienne du corps de classes » (ou « programme de Langlands »).
+On démontre que le nombre de solutions
+dans $𝐅_p$ de l'équation $x³=2$ 
+est $1+a_p$, où les $a_n$ sont les coefficients
+de la série formelle
+\[
+x∏_{n=1}^∞ \big((1-x^{6n})(1-x^{18n})\big)=∑^∞_{n=1} a_n x^n.
+\]
+% cf. nouveau livre de Katô p. 36. À déplacer ?
+\end{remarque2}
+
+\begin{remarques2}\label{remarque-periodicite-symbole-legendre}
+La loi de réciprocité quadratique et la formule complémentaire (ainsi
+que la formule \ref{formule-symbole-legendre} pour le cas $a=-1$)
+permettent de conclure que $\Legendre{a}{p}$, qui est évidemment une
+fonction périodique de $a$ à $p$ fixé, est aussi, ce qui n'était pas
+évident a priori, une fonction périodique de $p$ à $a$ fixé (au sens
+où il existe un entier $T$ ne dépendant que de $a$ tel que si $p,p'$
+sont premiers impairs et $p \equiv p' \pmod{T}$ alors $\Legendre{a}{p}
+= \Legendre{a}{p'}$) ; plus précisément, il admet pour période $T =
+4|a|$ (cela sera démontré en \ref{proprietes-symbole-jacobi}
+ci-dessous).  Ceci peut inciter à vouloir donner un sens à
+$\Legendre{a}{n}$ dans des cas où $n$ n'est plus nécessairement
+premier, en appliquant cette périodicité (par exemple, puisque
+$\Legendre{3}{p} = +1$ pour tout premier $p \equiv 1 \pmod{12}$, on
+est tenté de convenir que $\Legendre{3}{25} = +1$ et $\Legendre{3}{85}
+= +1$ même si $25$ et $85$ ne sont pas premiers et que $3$ n'est même
+pas un carré dans $\ZZ/25\ZZ$ ni $\ZZ/85\ZZ$).  Le symbole de Jacobi
+constitue une telle généralisation du symbole de Legendre :
+\end{remarques2}
+
+\subsection{Symboles de Jacobi et de Kronecker}
+
+\begin{definition2}\label{definition-symbole-jacobi}
+Pour tout $a \in \ZZ$ et tout $b \in \NN$ impair, on
+appelle \emph{symbole de Jacobi} de $a$ et $b$, et on note
+$\Legendre{a}{b}$, le symbole défini par $\Legendre{a}{b}
+= \Legendre{a}{p_1}\cdots \Legendre{a}{p_k}$ où $b = p_1\cdots p_k$
+avec $p_i$ des nombres premiers impairs, et où $\Legendre{a}{p_i}$
+désigne alors le symbole de
+Legendre (\ref{definition-symbole-legendre}).
+\end{definition2}
+
+\begin{proposition2}\label{proprietes-symbole-jacobi}
+Le symbole de Jacobi défini en \ref{definition-symbole-jacobi} a les
+propriétés suivantes :
+\begin{itemize}
+\item On a $\Legendre{a}{b} = 0$ si et seulement si $a,b$ sont
+premiers entre eux.
+\item Pour tous $a,a',b \in \ZZ$ avec $b$ positif impair, on a
+$\Legendre{aa'}{b} = \Legendre{a}{b} \Legendre{a'}{b}$.
+\item Pour tous $a,b,b' \in \ZZ$ avec $b,b'$ positifs impairs, on a
+$\Legendre{a}{bb'} = \Legendre{a}{b} \Legendre{a}{b'}$.
+\item À $b$ positif impair fixé, la fonction $\Legendre{a}{b}$ est
+périodique admettant $b$ pour période.
+\item À $a \neq 0$ fixé, la fonction $\Legendre{a}{b}$ est périodique
+admettant $4|a|$ pour période, et même $2|a|$ si $a \equiv 1
+\pmod{4}$ et $|a|$ si $a \equiv 0 \pmod{4}$.
+\item Pour tout $b$ positif impair, on a $\Legendre{-1}{b} =
+(-1)^{(b-1)/2}$.
+\item Pour tout $b$ positif impair, on a $\Legendre{2}{b} =
+(-1)^{(b^2-1)/8}$.
+\item Pour tous $a,b$ positifs impairs, on a
+$\Legendre{a}{b} \Legendre{b}{a} = (-1)^{(a-1)(b-1)/4}$.
+\end{itemize}
+\end{proposition2}
+\begin{proof}
+Les deux premières propriétés découlent immédiatement des propriétés
+correspondantes du symbole de Legendre.  La troisième propriété est
+une conséquence immédiate de la définition.  La quatrième propriété
+(périodicité en $a$) découle de nouveau de la propriété correspondante
+du symbole de Legendre.  La propriété suivante (périodicité en $b$)
+sera démontrée en dernier.
+
+Les formules $\Legendre{-1}{b} = (-1)^{(b-1)/2}$, $\Legendre{2}{b} =
+(-1)^{(b^2-1)/8}$ et $\Legendre{a}{b} \Legendre{b}{a} =
+(-1)^{(a-1)(b-1)/4}$ résultent des formules correspondantes pour le
+symbole de Legendre
+(\ref{formule-symbole-legendre}, \ref{formule-complementaire}
+et \ref{loi-reciprocite-quadratique}) et du fait que ces formules sont
+multiplicatives en $b$.
+
+Montrons enfin que $\Legendre{a}{b}$ est périodique en $b$ avec les
+périodes annoncées.  Si $a$ est positif impair, on a $\Legendre{a}{b}
+= (-1)^{(a-1)(b-1)/4} \Legendre{b}{a}$ comme on vient de le voir, et
+le membre de droite admet $4a$ pour période ou même $2a$ si $a \equiv
+1 \pmod{4}$ ; si $a = -1$ alors $\Legendre{-1}{b}$ est périodique de
+période $4$ et on en déduit le résultat pour tout $a$ impair.  Enfin,
+si $a = 2^v a'$ avec $a'$ impair, on a $\Legendre{a}{b}
+= \Legendre{2}{b}^v \Legendre{a'}{b}$.  Pour $v=1$ (cas où $a \equiv
+2 \pmod{4}$), le premier facteur a pour période $8$ et le second admet
+la période $4|a'|$, donc le produit admet la période $8|a'| = 4|a|$ ;
+pour $v=2$, le premier facteur est constant et le second admet la
+période $4|a'|$ donc le produit admet la période $4|a'| = |a|$ ; et
+pour $v\geq 3$, le premier facteur admet la période $8$ et le second
+la période $4|a'|$, donc le produit admet la période $8|a'|$
+donc $|a|$.
+\end{proof}
+
+\begin{remarques2}
+\begin{itemize}
+\item Comme on l'a déjà illustré
+en \ref{remarque-periodicite-symbole-legendre} par l'exemple de
+$\Legendre{3}{25} = +1$ et $\Legendre{3}{85} = +1$, on peut très bien
+avoir $\Legendre{a}{b} = +1$ sans que $a$ soit un carré
+dans $\ZZ/b\ZZ$.  En revanche, si $\Legendre{a}{b} = -1$ (avec $b$
+positif impair) alors $a$ n'est pas un carré dans $\ZZ/b\ZZ$ puisque
+$a$ n'est pas un carré modulo l'un des facteurs premiers de $b$.
+Voir cependant \ref{symbole-de-jacobi-et-corps-finis} ci-dessous.
+\item La formule \ref{formule-symbole-legendre} n'est pas valable en
+général pour le symbole de Jacobi, même si $a$ est effectivement un
+carré modulo $b$ (le nombre noté $p$
+en \ref{formule-symbole-legendre}) : par exemple, $\Legendre{11}{35} =
++1$, et de fait $11 \equiv 9^2 \pmod{35}$, pourtant
+$11^{(35-1)/2} \equiv 16 \pmod{35}$.
+\end{itemize}
+\end{remarques2}
+
+La proposition suivante est utile pour certains calculs, mais elle est
+vraie pour des raisons essentiellement triviales :
+\begin{proposition2}\label{symbole-de-jacobi-et-corps-finis}
+Soit $q$ une puissance d'un nombre premier $p$ impair, et $a \in \ZZ$
+non multiple de $p$.  Alors $a$ est un carré dans $\FF_q$ si et
+seulement si $\Legendre{a}{q} = +1$ où $\Legendre{a}{q}$ désigne le
+symbole de Jacobi.
+\end{proposition2}
+\begin{proof}
+Écrivons $q = p^r$.  Si $r$ est pair alors $\Legendre{a}{q}
+= \Legendre{a}{p}^2 = +1$, et $a$ est bien un carré dans $\FF_q$
+d'après \ref{carres-extensions-corps-finis}.  Si $r$ est impair alors
+$\Legendre{a}{q} = \Legendre{a}{p}^r = \Legendre{a}{p}$, et $a$ est un
+carré dans $\FF_q$ si et seulement s'il l'est dans $\FF_p$ de nouveau
+d'après \ref{carres-extensions-corps-finis}.
+\end{proof}
+
+\begin{remarque2}
+On définit parfois une généralisation encore plus poussée des symboles
+de Legendre et de Jacobi : le \emph{symbole de Kronecker}
+$\Legendre{a}{b}$ défini pour tous $a,b\in\ZZ$.  Celui-ci est défini
+en écrivant $b = u p_1\cdots p_k$ avec $u \in \{\pm 1\}$ et $p_i$ des
+nombres premiers (cette fois $p_i=2$ est admis), où $\Legendre{a}{p}$
+désigne le symbole de Legendre (\ref{definition-symbole-legendre}) si
+$p$ est premier impair, et de plus :
+\[\Legendre{a}{2} = \left\{
+\begin{array}{ll}
+0&\textrm{si $a$ est pair}\\
+(-1)^{(a^2-1)/8}&\textrm{si $a$ est impair}\\
+\end{array}
+\right.\]
+\[\Legendre{a}{-1} = \left\{
+\begin{array}{ll}
+1&\textrm{si $a\geq 0$}\\
+-1&\textrm{si $a<0$}\\
+\end{array}
+\right.\]
+et enfin
+\[\Legendre{a}{0} = \left\{
+\begin{array}{ll}
+1&\textrm{si $a = \pm 1$}\\
+0&\textrm{sinon}\\
+\end{array}
+\right.\]
+Le prix à payer pour une telle généralisation est principalement de
+perdre la périodicité de $\Legendre{a}{b}$ par rapport à $b$ lorsque
+$a \equiv -1 \pmod{4}$ (ainsi que la périodicité par rapport à $a$
+lorsque $b \leq 0$).  En fait, le choix de $\Legendre{a}{2} =
+(-1)^{(a^2-1)/8}$ (pour $a$ impair) est quelque peu arbitraire, et le
+symbole de Kronecker ne possède pas le caractère naturel du symbole de
+Jacobi.  Il vérifie néanmoins les propriétés suivantes dont la
+vérification est laissée au lecteur :
+\begin{itemize}
+\item On a $\Legendre{a}{b} = 0$ si et seulement si $a,b$ sont
+premiers entre eux.
+\item Pour tous $a,a',b \in \ZZ$, on a $\Legendre{aa'}{b}
+= \Legendre{a}{b} \Legendre{a'}{b}$.
+\item Pour tous $a,b,b' \in \ZZ$, on a $\Legendre{a}{bb'}
+= \Legendre{a}{b} \Legendre{a}{b'}$ sauf éventuellement si $a=-1$ et
+$bb'=0$.
+\item À $b>0$ fixé, la fonction $\Legendre{a}{b}$ est périodique
+admettant $4b$ pour période, et même $b$ si $b \not\equiv 2 \pmod{4}$.
+\item À $a \neq 0$ fixé, la fonction $\Legendre{a}{b}$ est périodique
+admettant $4|a|$ pour période si $a \not\equiv -1 \pmod{4}$, et même
+$|a|$ si $a \equiv 0,1 \pmod{4}$.
+\end{itemize}
+\end{remarque2}
+
+
+\section{Factorisation de polynômes sur les corps finis}\label{factorisation-polynomes-corps-finis}
+
+On a vu dans la section \ref{equations-quadratiques-corps-finis}
+comment calculer algorithmiquement des racines carrées (ou, en
+caractéristique $2$, des ``racines $\wp$-ièmes'') dans un corps fini
+et, par conséquent, comment résoudre n'importe quelle équation
+quadratique.  On se propose maintenant d'étudier la question plus
+générale de la factorisation des polynômes sur un corps fini.
+
+On peut évidemment supposer unitaire le polynôme $f$ à factoriser.
+Par ailleurs, dans la plupart des réductions qui suivront, notre but
+sera simplement de produire soit une factorisation non triviale $f =
+f_1 f_2$ (avec $\deg f_1, \deg f_2 > 0$) soit une preuve du fait que
+$f$ est irréductible (pour cela on connaît déjà le test de Rabin,
+cf. \refext{Fin}{critere-rabin}).  Pour obtenir une factorisation complète, il
+suffira alors d'appliquer récursivement l'algorithme à $f_1$ et $f_2$.
+
+\subsection{Calcul de la partie sans facteur carré}
+
+\subsubsection{}\label{rappels-polynomes-sans-facteurs-carres-corps-finis} Dans
+un premier temps, étudions la question de trouver la partie sans
+facteur carré d'un polynôme : on rappelle qu'un $f \in \FF_q[X]$ est
+dit \emph{sans facteur carré} lorsqu'il n'est divisible par le carré
+d'aucun polynôme autre qu'une constante ou, de façon équivalente, lorsque tous
+les facteurs apparaissent avec multiplicité ($0$ ou) $1$ dans la
+décomposition en facteurs irréductibles de $f$.  La \emph{partie sans
+facteur carré} de $f$ est le polynôme de plus grand degré (unitaire,
+disons) divisant $f$ et sans facteur carré, c'est-à-dire, le produit
+de tous les irréductibles unitaires divisant $f$ chacun avec
+multiplicité $1$.  Sur un corps parfait (\refext{Alg}{corps-parfait}),
+tous les polynômes irréductibles étant séparables, dire d'un polynôme
+qu'il est « séparable » ou « sans facteur carré » sont équivalents.
+
+Dans ce qui suit, on fait la convention que le pgcd de deux polynômes
+est toujours choisi unitaire.  On rappelle qu'on peut le calculer au
+moyen de l'algorithme d'Euclide étendu.
+
+\begin{proposition2}\label{partie-sans-facteur-carre-polynomes-corps-finis}
+Soit $f \in \FF_q[X]$ (où $q = p^r$) unitaire, et soit $f = \prod_i
+h_i^{v_i}$ sa décomposition en facteurs irréductibles (avec $h_i$
+unitaire irréductible).  Alors :
+\begin{itemize}
+\item le polynôme $f$ est sans facteur carré si et seulement si
+$\pgcd(f,f') = 1$ ;
+\item si $u = \pgcd(f,f')$, alors $f/u = \prod_{v_i\not\equiv
+0\pmod{p}} h_i$ (autrement dit, $f/u$ est le produit de tous les
+facteurs unitaires irréductibles divisant $f$ et dont la multiplicité
+$v_i$ dans $f$ n'est pas multiple de $p$, chacun avec
+multiplicité $1$) : en particulier, $f/u$ est un facteur de $f$ sans
+facteur carré ;
+\item si $N$ est suffisammment grand, et $N = \deg f$ suffit, alors le polynôme
+$f_1 = f/\pgcd(f,(f/u)^N)$ vaut aussi $u/\pgcd(u,(f/u)^N)$, et $f_1
+= \prod_{v_i \equiv 0\pmod{p}} h_i^{v_i}$ (autrement dit, $f_1$ est la
+partie de la décomposition en facteurs irréductibles de $f$ formée des
+irréductibles dont la multiplicité $v_i$ dans $f$ est multiple
+de $p$) : en particulier, $f_1$ est une puissance $p$-ième dans $\FF_q[X]$.
+\end{itemize}
+\end{proposition2}
+\begin{proof}
+Si $f = \prod_i h_i^{v_i}$, on a $f' = \sum_i v_i h_i' h_i^{v_i-1}
+\prod_{j\neq i} h_j^{v_j}$.  Fixons un $i_0$ : tous les termes de
+cette somme sont multiples de $h_{i_0}^{v_{i_0}}$, sauf peut-être
+celui où $i = i_0$.  Si $v_{i_0} \neq 0$ dans $\FF_q$ (c'est-à-dire si
+$p$ ne divise pas $v_{i_0}$) alors $v_{i_0} h_{i_0}'
+h_{i_0}^{v_{i_0}-1}$ est multiple de $h_{i_0}^{v_{i_0}-1}$ mais pas de
+$h_{i_0}^{v_{i_0}}$ puisque $h_i$ est séparable (car $\FF_q$ est
+parfait) : ainsi, sous cette hypothèse $v_{i_0} \neq 0$, le polynôme
+$f'$ est multiple de $h_{i_0}^{v_{i_0}-1}$ mais pas de
+$h_{i_0}^{v_{i_0}}$.  En revanche, si $v_{i_0} = 0$ dans $\FF_q$
+(c'est-à-dire si $p$ divise $v_{i_0}$) alors $f'$ est multiple
+de $h_{i_0}^{v_{i_0}}$.  Tout ceci mis prouve que $u = \pgcd(f,f')
+= \prod_i h_i^{v_i - 1 + \rho_i}$ où $\rho_i = 1$ si $p|v_i$ et
+$\rho_0 = 0$ sinon.  On a donc $f/u = \prod_i h_i^{1-\rho_i}$.  Ceci
+prouve les deux premières affirmations.
+
+La multiplicité de $h_i$ dans $\pgcd(f,(f/u)^N)$ vaut donc $\min(v_i,
+N(1-\rho_i))$, c'est-à-dire $(1-\rho_i)v_i$ si $N$ est supérieur ou
+égal à $\max(v_i)$ (et en particulier s'il est supérieur ou égal à
+$\deg f$).  De même, la multiplicité de $h_i$ dans $\pgcd(u,(f/u)^N)$
+vaut $\min(v_i-1+\rho_i, N(1-\rho_i))$, c'est-à-dire
+$(1-\rho_i)(v_i-1)$ si $N$ est supérieur ou égal à $\max(v_i-1)$ (et
+en particulier s'il est supérieur ou égal à $\deg f$).  On a donc
+$f/\pgcd(f,(f/u)^N) = u/\pgcd(u,(f/u)^N) = \prod_i h_i^{\rho_i v_i}$,
+ce qui prouve la troisième affirmation.
+\end{proof}
+
+\begin{remarques2}\label{algorithme-partie-sans-facteur-carre-polynomes-corps-finis}
+Cette proposition fournit un algorithme permettant de calculer la
+partie sans facteur carré $\prod_i h_i$ de $f$ : elle est égale à
+$f/u$ fois la partie sans facteur carré de la racine $p$-ième
+de $f_1$.  Pour calculer $f_1$, on fait une remarque semblable à celle
+soulevée en \refext{Fin}{remarques-critere-rabin} : il n'est pas nécessaire de
+calculer $(f/u)^N$ en tant que polynôme, mais seulement modulo $f$ (ou
+modulo $u$) puisqu'il s'agit d'appliquer l'algorithme d'Euclide étendu
+pour $\pgcd(f,(f/u)^N)$ (ou $\pgcd(u,(f/u)^N)$), et pour cela on
+applique un algorithme d'exponentiation rapide.  Calculer la racine
+$p$-ième de $f_1$ est facile : on sait que $f_1$ s'écrit $\sum_j a_j
+X^{pj}$, et sa racine $p$-ième est alors $\sum_j \root p\of{a_j} X^j$,
+avec $\root p\of{a_j} = a_j^{p^{r-1}}$ si $q = p^r$.  Enfin, une fois
+calculée la racine $p$-ième de $f_1$, on applique récursivement le
+même algorithme (le degré ayant décru strictement) pour en calculer la
+partie sans facteur carré.
+
+Mieux que calculer la partie sans facteur carrée de $f$, cette
+proposition fournit déjà parfois une factorisation non triviale de
+celle-ci, lorsque certaines mais pas toutes les multiplicités $v_i$
+des $h_i$ dans $f$ sont multiples de $p$.
+
+Une fois calculée la partie sans facteur carré $f_0$ de $f$, il est
+aisé de calculer la partie $\prod_{v_i=v} h_i$ formée par les facteurs
+irréductibles de multiplicité exactement $v$ : par exemple,
+$\pgcd(f,f_0^v)/\pgcd(f,f_0^{v-1}) = \prod_{v_i \geq v} h_i$ comme on
+le vérifie aisément, donc $\pgcd(f,f_0^v)^2/\penalty0
+(\pgcd(f,f_0^{v+1}) \penalty100\, \pgcd(f,f_0^{v-1})) = \prod_{v_i=v}
+h_i$.  (Mais généralement, on cherchera plutôt à trouver tous les
+facteurs irréductibles de $f_0$, et ensuite à calculer leur
+multiplicité dans $f$.)
+\end{remarques2}
+
+On pourra désormais supposer, pour la question de calculer la
+décomposition en facteurs irréductibles d'un polynôme, que celui-ci
+est sans facteur carré.
+
+\subsection{Décomposition en degrés distincts}
+
+\begin{proposition2}\label{decomposition-degres-distincts-polynomes-corps-finis}
+Soit $f \in \FF_q[X]$ unitaire et sans facteur carré, et soit $f
+= \prod_i h_i$ sa décomposition en facteurs irréductibles (avec $h_i$
+unitaire irréductible).  On définit par récurrence $f_1 = f$ et
+$f_{r+1} = f_r/g_r$ où $g_r = \pgcd(f_r, X^{q^r}-X)$.  Alors $g_r$ est
+le produit $\prod_{\deg h_i = r} h_i$ des facteurs unitaires
+irréductibles de $f$ dont le degré est exactement $r$.  (En
+particulier, $g_1$ a toutes les racines de $f$, et $g_r$ n'a aucune
+racine pour $r>1$.)
+\end{proposition2}
+\begin{proof}
+On rappelle la proposition \refext{Fin}{factorisation-x-q-r-x} : le polynôme
+$X^{q^r}-X$ est le produit de tous les polynômes unitaires
+irréductibles sur $\FF_q$ dont le degré divise $r$.  De cela il
+résulte que (pour $f_r$ un polynôme quelconque) $\pgcd(f_r,
+X^{q^r}-X)$ est le produit de tous les polynômes unitaires
+irréductibles divisant $f_r$ et dont le degré divise $r$.  On montre
+alors par récurrence sur $r$ que $f_r$ est le produit $\prod_{\deg h_i
+\geq r} h_i$ des facteurs unitaires irréductibles de $f$ dont le degré
+est au moins $r$, et que $g_r$ est le produit $\prod_{\deg h_i=r} h_i$
+de ceux dont le degré est exactement $r$.
+\end{proof}
+
+\begin{remarques2}\label{algorithme-decomposition-degres-distincts-polynomes-corps-finis}
+Cette proposition est algorithmique : partant d'un polynôme $f_1 = f$
+unitaire sans facteur carré, on calcule successivement la suite de
+polynômes $g_r = \pgcd(f_r, X^{q^r}-X)$ et les quotients $f_{r+1} =
+f_r / g_r$, ce qui fournit une factorisation $g_1 g_2 g_3 \cdots$
+de $f$ dans laquelle on a la garantie que les facteurs irréductibles
+de chaque $g_r$ sont tous de même degré $r$ (et en particulier, le
+degré de $g_r$ doit être multiple de $r$).  On parle
+de \emph{décomposition en degrés distincts} de $f$.  De nouveau comme
+en \refext{Fin}{remarques-critere-rabin}, le calcul de $\pgcd(f_r, X^{q^r}-X)$
+par l'algorithme d'Euclide étendu commence par le calcul de $X^{q^r}$
+modulo $f_r$ au moyen d'un algorithme d'exponentiation rapide.
+
+Lorsque $\deg g_r = r$ pour un certain $r$, on a la garantie que ce
+$g_r$ est irréductible.  Dans le calcul des $g_r$, on peut s'arrêter
+dès que $\deg f_r < 2r$, et alors $g_r = f_r$ est irréductible (on lui
+a en quelque sorte appliqué le critère de Ben-Or \refext{Fin}{critere-ben-or})
+et tous les autres $g_s$ non calculés valent $1$.
+
+Dans l'application de cet algorithme, rien n'oblige de diviser par les
+pgcd avec $X^{q^r}-X$ dans l'ordre $r=1,2,3,\ldots$ : la seule chose
+nécessaire est que chaque $r$ soit visité après tous ses diviseurs ---
+n'importe quel ordre total prolongeant l'ordre partiel de divisibilité
+convient.
+
+Selon la nature des polynômes à factoriser, il est imaginable qu'il
+soit plus efficace d'appliquer immédiatement l'algorithme qu'on vient
+de décrire à un polynôme non supposé sans facteur carré, sans passer
+au préalable par un algorithme comme
+en \ref{algorithme-partie-sans-facteur-carre-polynomes-corps-finis}.
+Dans ce cas, en divisant un polynôme par son pgcd avec $X^{q^r}-X$ on
+n'a pas la garantie que le quotient n'ait plus aucun facteur de degré
+divisant $r$ : il convient donc d'itérer ce calcul (à $r$ fixé)
+jusqu'à ce que le pgcd vaille $1$).
+
+Si le but est simplement de trouver les racines de $f$, ou de
+déterminer s'il en a, le calcul de $g_1 = \pgcd(f, X^q-X)$ suffit.  À
+ce sujet, si $f = X^2 - D$ avec $D\neq 0$ en caractéristique impaire,
+on a $X^{q-1} \equiv D^{(q-1)/2} \pmod{f}$, donc $g_1 = \pgcd(f,
+X^q-X)$ vaut $1$ ou $f$ selon que $D^{(q-1)/2}$ vaut $1$ ou non, et
+ceci fournit une nouvelle démonstration du fait que $D \neq 0$ est un
+carré dans $\FF_q$ (avec $q$ impair) exactement lorsque $D^{(q-1)/2} =
+1$.
+\end{remarques2}
+
+\subsection{Algorithme de Cantor-Zassenhaus}
+
+\subsubsection{} Grâce au travail déjà effectué, on peut maintenant
+supposer, s'il s'agit de factoriser un polynôme $g \in \FF_q[X]$, que
+celui-ci est produit de facteurs irréductibles de même degré : $g =
+h_1 \cdots h_s$ avec $h_i$ unitaire irréductible et $\deg h_i = r$ (et
+$\deg g = rs$).  On sait alors que $\FF_q[X]/(g) \cong (\FF_{q^r})^s$,
+même si on ne peut pas expliciter un tel isomorphisme en l'ignorance
+de la décomposition en facteurs irréductibles de $g$.  Notre but est
+de produire un élément $u$ de $\FF_q[X]/(g)$ dont l'image dans
+$(\FF_{q^r})^s$ par cet isomorphisme ait certaines composantes nulles,
+mais pas toutes, car alors $\pgcd(g,u)$ (ceci désignant par abus de
+langage le pgcd de $g$ avec un représentant quelconque de $u$ dans
+$\FF_q[X]$) sera multiple de certains des $h_i$ mais non de tous, ce
+qui fournit une factorisation non triviale de $g$.  L'algorithme de
+Cantor-Zassenhaus, que nous allons maintenant décrire, fournit un tel
+élément $u$ de la façon suivante (pour $q$ impair) : en partant d'un
+élément $y \in \FF_q[X]/(g)$ tiré au hasard, s'il ne répond pas déjà à
+ce qu'on recherche (c'est-à-dire, si toutes ses composantes dans
+$(\FF_{q^r})^s$ ne sont pas nulles) alors $t = y^{(q^r-1)/2}$ a toutes
+ses composantes égales à $1$ ou $-1$
+d'après \ref{denombrement-carres-f-q}, et si elles ne sont pas égales
+(c'est-à-dire si $t = y^{(q^r-1)/2}$ ne vaut pas $1$ ou $-1$) alors $u
+= t-1$ fournira un élément comme recherché.  La proposition suivante
+explicite cette idée :
+
+\begin{proposition2}\label{proposition-algorithme-cantor-zassenhaus}
+Soit $q$ une puissance d'un nombre premier impair, et soit
+$g \in \FF_q[X]$ de degré $rs$, unitaire sans facteur carré dont tous
+les facteurs irréductibles ont le même degré $r$.  Si $y$ est un
+élément quelconque de $\FF_q[X]/(g)$ et qu'on pose $t = y^{(q^r-1)/2}$
+(dans $\FF_q[X]/(g)$), alors une et une seule des affirmations
+suivantes est vraie :
+\begin{itemize}
+\item on a $y=0$,
+\item le polynôme $\pgcd(g,y)$ (où par $y$ on entend n'importe quel
+représentant de celui-ci dans $\FF_q[X]$) est différent de $1$ et
+de $g$ (et fournit donc une factorisation non triviale de $g$),
+\item on a $t=\pm 1$,
+\item le polynôme $\pgcd(g,t-1)$ (où par $t-1$ on entend n'importe quel
+représentant de celui-ci dans $\FF_q[X]$) est différent de $1$ et
+de $g$ (et fournit donc une factorisation non triviale de $g$).
+\end{itemize}
+De plus, les nombres de $y \in \FF_q[X]/(g)$ vérifiant chacune de ces
+quatre affirmations valent respectivement : $1$, $q^{rs} - (q^r-1)^s -
+1$, $\frac{1}{2^{s-1}}(q^r-1)^s$ et $(1-\frac{1}{2^{s-1}})(q^r-1)^s$.
+\end{proposition2}
+\begin{proof}
+L'hypothèse sur $g$ et le théorème chinois assurent l'existence d'un
+isomorphisme d'anneaux $\psi \colon \FF_q[X]/(g) \to (\FF_{q^r})^s$.
+
+Dire que $y$ n'est pas nul (c'est-à-dire si $\psi(y)$ n'est pas nul),
+mais que certaines des composantes de $\psi(y)$ sont néanmoins nulles,
+signifie exactement que certains mais pas tous les $h_i$ divisent $y$
+(c'est-à-dire, n'importe quel représentant de $y$ dans $\FF_q[X]$), ce
+qui signifie encore que le polynôme $\pgcd(g,y)$ est différent de $1$
+et de $g$.  On a ainsi réparti les $q^{rs}$ éléments $y$ de
+$\FF_q[X]/(g) \cong (\FF_{q^r})^s$ en $1$ élément nul, $q^{rs} -
+(q^r-1)^s$ dont au moins une composante de $\psi(y)$ est nulle, et
+$(q^r-1)^s$ éléments non nuls dans chacun des $s$ facteurs chinois.
+On se place à présent dans ce dernier cas.
+
+Pour tout élément non nul $z$ de $\FF_{q^r}$ on a $z^{(q^r-1)/2} = \pm
+1$, ce nombre valant $+1$ pour $\frac{1}{2}(q^r-1)$ éléments $z$, et
+$-1$ pour les $\frac{1}{2}(q^r-1)$ autres
+(cf. \ref{denombrement-carres-f-q}).  On en déduit que si $t =
+y^{(q^r-1)/2}$, alors chacune des composantes de $\psi(t)$ vaut $+1$
+ou $-1$.  Et chacune des $2^s$ combinaisons de signes est réalisée
+pour $\frac{1}{2^s}(q^r-1)^s$ éléments (parmi les $(q^r-1)^s$
+considérés) de $\FF_q[X]/(g) \cong (\FF_{q^r})^s$.  Lorsque toutes les
+composantes de $\psi(t)$ sont égales, ce qui se produit dans
+$\frac{1}{2^{s-1}}(q^r-1)^s$ cas, on a ainsi $t = \pm 1$.  Dans toute
+autre situation, certaines des composantes de $\psi(t)$ valent $+1$ et
+d'autres valent $-1$, c'est-à-dire que certaines mais pas toutes les
+composantes de $\psi(t-1)$ valent $0$, et ainsi le polynôme
+$\pgcd(g,t-1)$ est différent de $1$ et de $g$.
+\end{proof}
+
+\begin{remarques2}
+La proposition ci-dessus, et sa démonstration, sont rigoureusement
+parallèles à \ref{proposition-algorithme-legendre}, qu'elles
+généralisent.  Avant de discuter l'algorithme de Cantor-Zassenhaus qui
+en découle (et dont l'algorithme de Legendre de calcul des racines
+carrées est un cas particulier), décrivons maintenant la proposition
+correspondante en caractéristique $2$
+(généralisant \ref{proposition-algorithme-legendre-caracteristique-2}) :
+\end{remarques2}
+
+\begin{proposition2}\label{proposition-algorithme-cantor-zassenhaus-caracteristique-2}
+Soit $q = 2^r$ une puissance de $2$, et soit $g \in \FF_q[X]$ de
+degré $rs$, unitaire sans facteur carré dont tous les facteurs
+irréductibles ont le même degré $r$.  Si $y$ est un élément quelconque
+de $\FF_q[X]/(g)$ et qu'on pose $t = y + y^2 + y^4 + \cdots +
+y^{q^r/2}$ (dans $\FF_q[X]/(g)$), alors une et une seule des
+affirmations suivantes est vraie :
+\begin{itemize}
+\item on a $t \in \{0,1\}$,
+\item le polynôme $\pgcd(g,t)$ (où par $t$ on entend n'importe quel
+représentant de celui-ci dans $\FF_q[X]$) est différent de $1$ et
+de $g$ (et fournit donc une factorisation non triviale de $g$).
+\end{itemize}
+De plus, les nombres de $y \in \FF_q[X]/(g)$ vérifiant chacune de ces
+deux affirmations valent respectivement $\frac{1}{2^{s-1}}q^{rs}$ et
+$(1-\frac{1}{2^{s-1}})q^{rs}$.
+\end{proposition2}
+\begin{proof}
+L'hypothèse sur $g$ et le théorème chinois assurent l'existence d'un
+isomorphisme d'anneaux $\psi \colon \FF_q[X]/(g) \to (\FF_{q^r})^s$.
+
+Pour tout élément non nul $z$ de $\FF_{q^r}$ on a $z + z^2 + z^4
++ \cdots + z^{q^r/2} \in \{0, 1\}$, ce nombre valant $0$ pour
+$\frac{q^r}{2}$ éléments $z$, et $1$ pour les $\frac{q^r}{2}$ autres
+(cf. \ref{denombrement-artin-schreier-2-f-q}).  On en déduit que si $t
+= y + y^2 + y^4 + \cdots + y^{q^r/2}$, alors chacune des composantes
+de $\psi(t)$ vaut $0$ ou $1$.  Et chacune des $2^s$ combinaisons de
+signes est réalisée pour $\frac{1}{2^s}q^{rs}$ éléments (parmi les
+$q^{rs}$ au total) de $\FF_q[X]/(g) \cong (\FF_{q^r})^s$.  Lorsque
+toutes les composantes de $\psi(t)$ sont égales, ce qui se produit
+dans $\frac{1}{2^{s-1}}q^{rs}$ cas, on a ainsi $t \in \{0,1\}$.  Dans
+toute autre situation, certaines des composantes de $\psi(t)$ valent
+$0$ et d'autres valent $1$, c'est-à-dire que certaines mais pas toutes
+les composantes de $\psi(t)$ valent $0$, c'est-à-dire que certains
+mais pas tous les $h_i$ divisent $t$ (c'est-à-dire, n'importe quel
+représentant de $t$ dans $\FF_q[X]$), ce qui signifie encore que le
+polynôme $\pgcd(g,t)$ est différent de $1$ et de $g$.
+\end{proof}
+
+\subsubsection{}\label{algorithme-cantor-zassenhaus} Les
+propositions \ref{proposition-algorithme-cantor-zassenhaus} et \ref{proposition-algorithme-cantor-zassenhaus-caracteristique-2}
+conduisent à l'\emph{algorithme} suivant, dit de Cantor-Zassenhaus,
+permettant de factoriser un polynôme $g \in \FF_q[X]$, dont on a vu
+qu'on pouvait le supposer unitaire, sans facteur carré, et ayant tous
+ses facteurs irréductibles de même degré : dans un premier temps,
+tirer $y$ aléatoirement dans $\FF_q[X]/(g)$.  Puis calculer $t =
+y^{(q^r-1)/2}$ dans $\FF_q[X]/(g)$ (c'est-à-dire, calculer le reste de
+la division euclidienne de $X^{(q^r-1)/2}$ par $g$) par un algorithme
+d'exponentiation rapide dans cet anneau $\FF_q[X]/(g)$ ; resp., en
+caractéristique $2$, calculer $t = y + y^2 + \cdots + y^{q^r/2}$.  Si
+le résultat vaut $\pm 1$ (resp. $0$ ou $1$ en caractéristique $2$), on
+doit choisir un nouveau $y$ et recommencer ; sinon, calculer
+$\pgcd(g,t-1)$ (resp. $\pgcd(g,t)$ en caractéristique $2$) : ceci
+devrait fournir un facteur non trivial de $g$ ; quant au petit nombre
+(du moins si $q$ ou $s$ est grand) de $y$ situés dans le second cas
+de \ref{proposition-algorithme-cantor-zassenhaus} (problème qui ne se
+pose pas en caractéristique $2$), il peut soit être écarté \emph{a
+priori} en vérifiant avant de commencer si $\pgcd(g,y)$ fournit un
+facteur non trivial, soit plus vraisemblablement être traité \emph{a
+posteriori} en calculant $\pgcd(g,t)$ lorsque $\pgcd(g,t-1)$ n'a pas
+fourni le facteur attendu.
+
+\begin{remarque2}
+En rassemblant
+avec \ref{algorithme-partie-sans-facteur-carre-polynomes-corps-finis} (calcul
+de la partie sans facteur carré)
+et \ref{algorithme-decomposition-degres-distincts-polynomes-corps-finis} (décomposition
+en degrés distincts), l'algorithme de Cantor-Zassenhaus qu'on vient
+d'exposer permet de factoriser n'importe quel polynôme
+$g \in \FF_q[X]$.  Sans nous attarder sur la complexité de
+l'algorithme complet, disons simplement qu'elle est polynomiale en
+moyenne, et que seule cette dernière partie (l'algorithme de
+Cantor-Zassenhaus lui-même) utilise un élément de non-déterminisme et
+peut être mauvaise dans le pire cas (on peut imaginer de tirer au
+hasard beaucoup de $y$ avant d'obtenir une factorisation).  Il
+convient par ailleurs de signaler que, sans chercher à donner un sens
+précis à cette affirmation, si le polynôme $g$ est aléatoire, tout le
+travail de factorisation sera normalement effectué dans l'étape de
+factorisation en degrés distincts.
+\end{remarque2}
+
+\subsection{Applications}
+
+\subsubsection{} Parmi les nombreuses applications algorithmiques d'un
+algorithme quelconque de factorisation des polynômes sur les corps
+finis, attardons-nous à présent sur deux conséquences particulières,
+portant sur les représentations des corps finis comme des quotients.
+
+\begin{remarque2}\label{remarque-isomorphisme-explicite-corps-finis}
+Tout d'abord, considérons le problème de la conversion d'une
+représentation à une autre d'un corps fini : on rappelle
+(cf. \refext{Fin}{remarques-critere-rabin}) qu'on choisit généralement de
+représenter informatiquement un corps fini $\FF_{q^r}$ comme
+$\FF_q[X]/(h)$ (le plus souvent ici $q=p$ est premier) avec
+$h \in \FF_q[X]$ irréductible de degré $r$ (on peut trouver un tel $h$
+en tirant au hasard des polynômes de bon degré, et en testant leur
+irréductibilité au moyen par exemple du critère de Rabin ou de Ben-Or,
+jusqu'à obtenir un $h$ qui passe le test) ; si $h_1$ et $h_2$ sont
+deux polynômes irréductibles de même degré $r$, alors $\FF_q[X]/(h_1)$
+et $\FF_q[X]/(h_2)$ sont isomorphes (à $\FF_{q^r}$)
+d'après \ref{existence-et-unicite-corps finis} : on souhaite cependant
+parfois relier explicitement ces deux représentations de $\FF_{q^r}$,
+c'est-à-dire, trouver explicitement un isomorphisme
+$\FF_q[X]/(h_1) \buildrel\sim\over\to \FF_q[X]/(h_2)$.
+
+L'algorithme que nous avons vu permet de répondre à cette demande.  En
+effet, considérons le problème de factoriser $h_1$ dans $\FF_{q^r}$ vu
+comme $\FF_q[X]/(h_2)$ : on sait par avance que cette factorisation
+comportera $r$ facteurs linéaires, c'est-à-dire qu'il s'agit de
+trouver les $r$ racines de $h_1$ dans $\FF_q[X]/(h_2)$ ; en fait, on
+se contente de trouver \emph{une} racine $\theta$ (les autres
+s'obtenant, de toute façon, par applications successives de $\Frob_q$
+à $\theta$) : l'algorithme de Cantor-Zassenhaus, éventuellement adapté
+pour chercher à casser toujours le facteur de plus petit degré, permet
+de trouver un tel $\theta$.  Un isomorphisme
+$\FF_q[X]/(h_1) \buildrel\sim\over\to \FF_q[X]/(h_2)$ est alors fourni
+par $a \mapsto a(\theta)$ (où $a(\theta)$ désigne l'évaluation en
+$\theta$ de n'importe quel représentant dans $\FF_q[X]$ de
+$a \in \FF_q[X]/(h_1)$).
+\end{remarque2}
+
+\begin{exemple2}
+Pour illustrer la remarque précédente, considérons les deux polynômes
+$h_1 = X^4 + X + 1$ et $h_2 = X^4 + X^3 + X^2 + X + 1$ irréductibles
+de degré $4$ sur $\FF_2$.  En factorisant $h_1$ dans $\FF_2[X]/(h_2)$,
+on trouve $h_1 = (X-\theta)\,(X-\theta^2)\,(X-\theta^4)\,(X-\theta^8)$
+où $\theta, \theta^2, \theta^4, \theta^8$ sont les quatre racines
+$x^2+x$, $x^3+x+1$, $x^2+x+1$ et $x^3+x$ (ici, $x$ désigne la classe
+de $X$ dans $\FF_2[X]/(h_2)$).  L'isomorphisme décrit ci-dessus envoie
+alors, par exemple, la classe de $X^3$ dans $\FF_2[X]/(h_1)$ sur
+$\theta^3 = x^2 \in \FF_2[X]/(h_2)$.
+\end{exemple2}
+
+\begin{remarque2}\label{remarque-tours-corps-finis}
+Un problème apparenté est celui de l'aplatissement des tours de corps
+finis : si $g \in \FF_q[Y]$ est un polynôme irréductible de degré $s$
+sur $\FF_q$, et $h \in \FF_{q^s}[X]$ un polynôme irréductible de
+degré $t$ sur $\FF_{q^s} = \FF_q[Y]/(g)$ dont le ppcm des degrés
+sur $\FF_q$ des coefficients est égal à $s$.  On sait alors
+d'après \refext{Fin}{descindage-polynomes-tours-corps-finis} que $f
+= \prod_{i=0}^{s-1} \Frob_q^i(h) \in \FF_q[X]$ est irréductible de
+degré $st$, et que réciproquement
+(cf. \refext{Fin}{scindage-partiel-polynomes-corps-finis}) tout
+$f \in \FF_q[X]$ irréductible de degré $st$ s'obtient de cette forme
+pour un certain $h$ (le polynôme $g$ étant ici fixé) ; par ailleurs,
+l'algorithme de Cantor-Zassenhaus ou tout autre algorithme de
+factorisation des polynômes sur les corps finis permet de calculer $h$
+connaissant $f$ (en factorisant ce dernier dans $\FF_{q^s}[X]$).  On a
+alors deux présentations différentes du corps $\FF_{q^{st}}$ : soit
+comme $\FF_q[X]/(f)$ soit comme $\FF_{q^s}[X]/(h)$ où $\FF_{q^s}$ est
+lui-même vu comme $\FF_q[Y]/(g)$.  La question se pose de savoir
+comment convertir d'une représentation à l'autre, c'est-à-dire,
+expliciter un isomorphisme entre ces $\FF_q[X]/(f)$ et
+$\FF_{q^s}[X]/(h)$.
+
+Un isomorphisme $\psi \colon \FF_q[X]/(f) \to \FF_{q^s}[X]/(h)$ est
+aisé à décrire : donné $a \in \FF_q[X]$, on définit $\psi(\bar a)$
+comme la classe de $a$ (vu dans $\FF_{q^s}[X]$) modulo $h$,
+c'est-à-dire concrètement le reste de la division euclidienne de $a$
+par $h$ --- il est évident que ceci définit bien un morphisme
+d'anneaux, qui est injectif puisque tout élément de $\FF_q[X]$
+multiple de $h$ dans $\FF_{q^s}[X]$ est multiple de $f$ car ce dernier
+est irréductible, et par comparaison des cardinaux ce $\psi$ et bien
+un isomorphisme.  Notons que ce $\psi \colon \FF_q[X]/(f) \to
+(\FF_q[Y]/(g))[X]/(h)$ est uniquement caractérisé comme isomorphisme
+de $\FF_q$-algèbres (les polynômes $f,g,h$ étant fixés) par le fait
+que $\psi(X) = X$.
+
+Pour décrire l'isomorphisme réciproque, considérons la factorisation
+de $g$ dans $\FF_q[X]/(f)$ : il est scindé
+(cf. \refext{Fin}{racines-polynome-minimal-corps-fini}
+ou \refext{Fin}{scindage-partiel-polynomes-corps-finis}), et parmi ses racines
+il en existe exactement une, qu'on notera $z$, que $\psi$ envoie sur
+l'élément $y \in \FF_{q^s}$ classe de $Y$ dans $\FF_q[Y]/(g)$ (puisque
+$y$ est lui-même racine de $g$).  Alors $\psi^{-1}$ envoie la classe
+(dans $\FF_{q^s} = \FF_q[Y]/(g)$) de $a \in \FF_q[Y]$ sur $a(z)$, et
+comme il envoie $X$ sur $X$ on peut aisément calculer l'image
+par $\psi^{-1}$ d'un élément quelconque de $\FF_{q^s}[X]/(h)$.
+\end{remarque2}
+
+\begin{exemple2}
+Pour illustrer la remarque précédente, considérons le polynôme $f =
+X^4 + X + 1 \in \FF_2[X]$ : vu dans $\FF_4 = \FF_2[Y]/(g)$ où $g = Y^2
++ Y + 1$ (est le seul polynôme irréductible de degré $2$ sur $\FF_2$),
+le polynôme $f$ se factorise comme $h\, \Frob_2(h)$ où $h = X^2 + X +
+y$ et $\Frob_2(h) = X^2 + X + y+1$.  L'isomorphisme $\psi$ envoie, par
+exemple, la classe $x^3$ de $X^3$ dans $\FF_2[X]/(f)$ sur $(y+1)x +
+y \in \FF_4[X]/(h)$ car le reste de la division euclidienne de $X^3$
+par $X^2 + X + y$ (dans $\FF_4[X]$) est $(y+1)X + y$.  L'isomorphisme
+réciproque $\psi^{-1}$ envoie $y$ sur $z = x^2 + x$ puisque c'est
+visiblement celle des deux racines $x^2+x, x^2+x+1$ de $g$ dans
+$\FF_2[X]/(f)$ qui s'envoie sur $y$ par $\psi$.  On peut alors
+vérifier que $\psi^{-1}((y+1)x + y) = x^3$.
+\end{exemple2}
+
+\subsection{Algorithme de Berlekamp}
+
+\subsubsection{} Dans le même esprit que le critère d'irréductibilité
+de Butler \refext{Fin}{critere-butler} utilise des techniques d'algèbre
+linéaire effective à la place de la factorisation de $X^{q^r}-X$ qui
+sous-tend le critère de Rabin \refext{Fin}{critere-rabin}, on peut mettre
+en \oe{}uvre des techniques d'algèbre linéaire, également fondées sur
+l'étude du sous-$\FF_q$-espace vectoriel $\Ker(\Frob_q - \Id)$
+de $\FF_q[X]/(g)$, pour factoriser un polynôme $g$ (supposé sans
+facteur carré).
+
+\begin{definition2}\label{definition-algebre-berlekamp}
+Si $g \in \FF_q[X]$ est sans facteur carré, on appelle \emph{algèbre
+de Berlekamp} de $g$ le sous-$\FF_q$-espace vectoriel $\Ker(\Frob_q
+- \Id)$ (c'est-à-dire $\{y \in \FF_q[X]/(g) : y^q = y\}$)
+de $\FF_q[X]/(g)$, qui en est une sous-$\FF_q$-algèbre.
+\end{definition2}
+
+On a ainsi vu en \refext{Fin}{critere-butler} que $g$ est irréductible si et
+seulement si son algèbre de Berlekamp se réduit à $\FF_q$ (i.e., est
+de dimension $1$).  Le résultat suivant généralise ce fait :
+
+\begin{proposition2}\label{proposition-algorithme-berlekamp}
+Soit $g \in \FF_q[X]$ unitaire sans facteur carré.  Alors :
+\begin{itemize}
+\item la dimension $s$ sur $\FF_q$ de l'algèbre de Berlekamp $B_g$ de $g$
+est égale au nombre de facteurs unitaires irréductibles de $g$, et si
+$h_1,\ldots,h_s$ sont ces facteurs irréductibles alors l'isomorphisme
+chinois
+$\psi \colon \FF_q[X]/(g) \buildrel\sim\over\to \FF_q[X]/(h_1) \times \cdots \times \FF_q[X]/(h_s)$
+se restreint en un isomorphisme $B_g \buildrel\sim\over\to (\FF_q)^s$,
+\item de plus, pour tout $y \in B_g$, on a $g
+= \prod_{c\in\FF_q} \pgcd(g, y-c)$.
+\end{itemize}
+\end{proposition2}
+\begin{proof}
+Soit $g = h_1\cdots h_s$ la décomposition en facteurs irréductibles
+de $g$.  Alors le théorème chinois assure l'existence d'un
+isomorphisme
+$\psi \colon \FF_q[X]/(g) \buildrel\sim\over\to \FF_q[X]/(h_1) \times \cdots \times \FF_q[X]/(h_s)$,
+chacun des facteurs du membre de droite étant un corps $\FF_{q^{\deg
+h_i}}$ puisque $h_i$ est irréductible.
+D'après \refext{Fin}{petit-theoreme-fermat} et \refext{Fin}{unicite-corps-q-elements-pour-inclusion},
+on peut voir $B_g$ comme l'ensemble des éléments $y$ de $\FF_q[X]/(g)$
+tels que chaque composante de $\psi(y)$ soit dans $\FF_q$.  Ceci
+montre immédiatement la première affirmation ; quant à la seconde,
+elle résulte de ce que si $y \in \FF_q[X]/(g)$ alors $\pgcd(g,y)$ est
+le produit des $h_i$ tels que $y$ soit multiple de $h_i$ c'est-à-dire
+que la $i$-ième composante de $\psi(y)$ s'annule.
+\end{proof}
+
+\begin{remarques2}\label{algorithme-berlekamp}
+Lorsque $q$ est petit, la
+proposition \ref{proposition-algorithme-berlekamp} fournit telle
+quelle un algorithme de factorisation, dit de Berlekamp, pour les polynômes $g$ sans
+facteur carré dans $\FF_q[X]$ : on utilise des techniques d'algèbre
+linéaire pour trouver une $\FF_q$-base $\tau_1,\ldots,\tau_s$ de
+l'algèbre de Berlekamp $B_g = \Ker(\Frob_q - \Id)$ de $g$, puis, si
+$s>1$ de sorte qu'il y a une factorisation non triviale à effectuer,
+on tire au hasard un élément $y = c_1 \tau_1 + \cdots + c_s \tau_s \in
+B_g$ (avec $c_i \in \FF_q$) et on calcule les $\pgcd(g, y-c)$ pour les
+différents $c \in \FF_q$ : ceci fournira une factorisation non
+triviale de $y$ dès que les composantes de $\psi(y)$ ne sont pas
+toutes égales (où $\psi$ est l'isomorphisme $\psi \colon
+B_g \buildrel\sim\over\to (\FF_q)^s$ déduit de l'isomorphisme
+chinois), ce qui se produit pour $q^s - q$ des $q^s$ éléments $y$
+de $B_g$.
+
+Lorsque $q$ est grand, la proposition ne peut pas servir en tant que
+telle.  On peut cependant la combiner avec les mêmes idées
+qu'en \ref{proposition-algorithme-cantor-zassenhaus}
+(resp. \ref{proposition-algorithme-cantor-zassenhaus-caracteristique-2}
+en caractéristique $2$) : une fois tiré $y$ dans $B_g$, on calcule $t
+= y^{(q-1)/2}$ (resp. $t = y + y^2 + y^4 + \cdots + y^{q/2}$ en
+caractéristique $2$), et alors $\pgcd(g,t-1)$ (resp. $\pgcd(g,t)$) a
+une probabilité raisonnable de fournir un facteur non trivial de $g$
+(cf. \ref{algorithme-cantor-zassenhaus}, le rôle de l'algèbre linéaire
+étant essentiellement de pouvoir faire comme si $r=1$).
+\end{remarques2}
+
+
+\ifx\danslelivre\undefined
+\end{document}
+\fi