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/algo-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/algo-corps-finis.tex')
-rw-r--r-- | chapitres/algo-corps-finis.tex | 1549 |
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 |