%From - Thu Jun 15 09:49:34 2000
\documentclass[11pt]{amsart}
\usepackage{kb, a4wide}
\usepackage[theo]{kbexo}
\course{Préparation à l'agrégation}

\begin{document}
\agregtitle{Factorisation de polynômes sur des corps finis}
\section{Introduction}
La factorisation est l'un des points où l'analogie entre nombres entiers et
polynômes se rompt. Par exemple, en caractéristique nulle, on peut trouver la
partie sans facteurs carrés d'un polynôme (c'est-à-dire le produit de ses
facteurs irréductibles) en utilisant la notion de dérivée, et en
caractéristique positive, on peut aménager ce procédé. De plus, la notion de
degré, la structure d'algèbre dont est muni l'ensemble de polynômes sur un
corps, fournissent des outils importants pour la résolution du problème.

Nous allons voir deux algorithmes. Le premier utilise trois étapes: la
factorisation en un produit de polynômes sans facteurs carrés, la
factorisation en degrés distincts, puis la factorisation en degrés égaux
(algorithme de Cantor-Zassenhaus). La seconde utilise d'abord une
factorisation en produit de polynômes sans facteurs carrés, puis un
algorithme de factorisation dû à Berlekamp, qui utilise de l'algèbre
linéaire.

\section{Factorisation en degrés distincts}
Ce paragraphe décrit une factorisation de polynômes sans facteurs carrés en
un produit de polynômes de degrés distincts. On utilise le théorème suivant.
\begin{theo}
Pour tout $d\geq1$, $x^{q^d}-x\in\FM_q[x]$ est le produit de tous les
polynômes unitaires irréductibles de $\FM_q[x]$ dont le degré divise $d$.
\end{theo}

\begin{defi}\label{distincts}
La décomposition en degrés distincts d'un polynôme non
constant $f\in\FM_q[x]$ est la suite $(g_1,\dots,g_s)$ de polynômes,
où $g_i$ est le produit de tous les polynômes unitaires irréductibles
de degré $i$ qui divisent $f$, avec $g_s\ne1$.
\end{defi}

\misctitle{Exemple} $x^2+x,x^4+x^3+x+2$ est la décomposition en
degrés distincts de $f=x(x+1)(x^2+1)(x^2+x+2)\in\FM_3[x]$.

\medskip

Pour effectuer la factorisation en degrés distincts d'un polynôme
$f$ sans facteurs carrés, on peut définir les éléments
de $R=\FM_q[x]/(f)$, pour $i\geq0$~:
$h_i=x^{q^i}$, $f_0=f$, $g_i=(h_i-x,f_{i-1})$, $f_i=f_{i-1}/g_i$,
jusqu'à ce que $f_i=1$. On pose alors $s=i$ et la décomposition
cherchée est $(g_1,\dots, g_s)$.

\begin{theo}
Cet algorithme fonctionne, et utilise $O(sn^2\log(q))$ opérations
dans~$\FM_q$.
\end{theo}
\noindent On arrête l'algorithme dès que deg$f_i<2(i+1)$ : comme tous les
facteurs irréductibles de $f_i$ ont un degré supérieur ou égal à $i+1$, $f_i$
est donc irréductible dans ce cas.

\section{Factorisation en degrés égaux (algorithme de Cantor-Zassenhaus)}
Maintenant, voyons la factorisation en degrés égaux, pour factoriser les
polynômes produits par la factorisation en degrés distincts. L'algorithme
décrit ici ne fonctionne que si $q$ est impair.

\begin{lemme}
Soit $q$ une puissance d'un nombre premier impair, et soit $S=(\FM_q^*)^2$
l'ensemble des carrés de $\FM_q$. Alors $S$ est un sous-groupe de $\FM_q^*$
d'ordre $(q-1)/2$, égal à $\Ker \varphi$, où $\varphi$ est l'homomorphisme de
groupes de $\FM_q^*$ dans $\set{-1,1}$ qui à $a$ associe $a^{(q-1)/2}$.
\end{lemme}

Soit $f$ un polynôme unitaire de $\FM_q[x]$ de degré $n$, et soit $d\mid n$
tel que tous les facteurs irréductibles de $f$ ont degré $d$. On veut
trouver ces $r = n/d$ facteurs irréductibles. On écrit $f=f_1\dots f_r$, où
pour tout $i$, $f_i\in\FM_q[x]$ est unitaire irréductible de degré $d$. On
peut supposer que $r\geq2$, car sinon $f$ est irréductible. Grâce au théorème
chinois, on sait qu'il existe un isomorphisme d'algèbres
$$\chi\colon R\longrightarrow \FM_q[x]/(f_1)\times\dots\FM_q[x]/(f_r)
 \simeq (\FM_{q^d})^r.$$
Pour tout $a\in R$, on note $\chi_i(a)$ l'image de $a$ par la projection
sur le $i$-ème facteur. Si l'on trouve un polynôme $a$ tel que certains
$\chi_i(a)$ sont nuls et d'autres non, alors $(a,f)$ est un diviseur non
trivial de $f$.

Soit $e=(q^d-1)/2$. Pour tout $\alpha\in\FM_{q^d}^*$, $\alpha^e\in\{\pm1\}$,
les deux possibilités étant équiprobables. Si on tire $a\in R^*$ uniformément
au hasard, alors les $\chi_i(a)$ suivent des lois de probabilité uniformes
indépendantes sur $\FM_{q^d}^*$, et $\varepsilon_i=\chi_i(a^e)$ est égal à
$1$ ou $-1$, chacun avec une probabilité de $1/2$. Ainsi,
$$\chi(a^e-1)=(\varepsilon_1-1,\dots\varepsilon_r-1),$$
et $a^e-1$ décompose $f$, sauf si $\varepsilon_1=\dots=\varepsilon_r$,
ce qui arrive avec probabilité $2^{-r+1}\leq1/2$.
On procède de la façon suivante:
\begin{itemize}
\item On tire $a\in\FM_q[x]$ tel que $0 < \deg a < n$.

\item On pose $g_1=\pgcd(a,f)$. Si $g_1\ne1$, on retourne le facteur non
trivial $g_1$.

\item On calcule $b=a^{(q^d-1)/2}$ mod $f$.

\item On calcule $g_2=\pgcd(b-1,f)$. Si $g_2\ne 1,f$, alors on retourne
$g_2$. Sinon, on retourne «Échec».
\end{itemize}

\begin{theo}
Cet algorithme de Cantor-Zassenhaus répond «Échec» avec une probabilité
inférieure à $2^{1-r}\leq1/2$, où $r=n/d\geq2$, ou sinon donne un facteur non
trivial de $f$. Il utilise $O(dn^2\log(q))$ opérations dans $\FM_q$.
\end{theo}
Ainsi, si l'on fait tourner l'algorithme $k$ fois, la probabilité de ne pas
trouver de facteurs est inférieure à $2^{(1-r)k}\leq2^{-k}$. Cet algorithme
donne $2$ facteurs. Si on veut juste un facteur irréductible, on peut
appliquer l'algorithme récursivement sur le plus petit facteur.
Habituellement, on veut les $r$ facteurs irréductibles, et donc on applique
l'algorithme récursivement sur tous les facteurs réductibles (de degré $> d$).

\begin{theo}
Par cette méthode, on factorise un polynôme de degré $n=rd$ avec $r$ facteurs
irréductibles de degré $d$ en utilisant $O(dn^2\log q\log r)$ opérations dans
$\FM_q$ en moyenne.
\end{theo}

Pour montrer cela, on peut illustrer la méthode par un arbre. Les noeuds de
l'arbre sont des facteurs de $f$. La racine est $f$ et les facteurs
irréductibles sont les feuilles. Si l'algorithme de Cantor-Zassenhaus répond
«Échec», alors le noeud correspondant a exactement un enfant avec le même
polynôme. Sinon, il a deux enfants qui contiennent le facteur trouvé et son
cofacteur. Le produit sur tous les noeuds à un niveau de l'arbre est égal à
$f$, donc la somme des degrés correspondants est $n$. Un noeud de
degré $m$ utilise $O(dm^2\log q)$ opérations dans $\FM_q$, donc le coût total
d'un niveau donné est de $O(dn^2\log q)$ opérations.

Montrons maintenant que la profondeur moyenne de l'arbre est en $O(\log r)$.
Soient $g$ et $g'$ deux facteurs irréductibles de $f$. La probabilité que
l'algorithme de Zassenhaus sépare $g$ et $g'$ est supérieure à $1/2$ (s'ils
n'ont pas été séparés auparavant). Donc, la probabilité pour que $g$ et $g'$
ne soient pas encore séparés à la profondeur $k$ de l'arbre est au plus
$2^{-k}$. C'est valable pour tout couple de facteurs irréductibles de $f$.
Comme il y a $(r^2-r)/2\leq r^2$ tels couples, la probabilité $p_k$ que tous
les facteurs irréductibles ne sont pas séparés à la profondeur $k$ de l'arbre
est au plus $r^22^{-k}$. Mais $p_k$ est en fait la probabilité pour que
l'arbre soit de profondeur supérieure ou égale à $k$, et $p_{k-1}-p_k$ est la
probabilité pour que l'arbre soit de profondeur exactement $k$. Donc la
profondeur moyenne de l'arbre est égale à
$$\sum_{k\geq1}k(p_{k-1}-p_k)=\sum_{k\geq0}p_k \leq s + 2,\quad
\text{où $s = \ceil{2\log_2 r}$}.$$
Pour $k<s$, on a utilisé le fait que $p_k\leq1$; pour $k\geq s$, le fait que
$p_k\leq r^2 2^{-k}$.

\section{Un algorithme complet de factorisation}
Soit $f$ un polynôme qui n'est pas nécessairement sans facteurs carrés. On
peut déterminer sa partie sans facteurs carrés, par un algorithme décrit dans
le paragraphe suivant.

Mais on peut aussi directement appliquer directement les algorithmes décrits
dans le paragraphe précédent. Ces algorithmes donnent la factorisation en
facteurs irréductibles de la partie sans facteur carrée de $f$. Ensuite, il
suffit de chercher la valuation de $f$ pour chacun de ces facteurs
irréductibles.

\medskip

Voyons le coût en opérations dans $\FM_q$. Il est dominé par $n^3\log q$ pour
la factorisation en degrés distincts. Ensuite, on applique l'algorithme de
Cantor-Zassenhaus aux différents facteurs $g_1,\dots, g_s$ trouvés,
respectivement de degrés $m_1,\dots, m_s$. Chacune de ces applications coûte
au plus
$$O\paren{im_i^2\log q\log(m_i/i)}$$
opérations dans $\FM_q$. Comme
$$i\log(m_i/i)=m_i\frac{\log(m_i/i)}{m_i/i}\leq m_i,$$
le coût total est en $O(n^3\log q)$. L'étape finale, qui trouve les
valuations des facteurs irréductibles, a un coût inférieur. L'algorithme
complet est en $O(n^3\log q)$.

\section{Factorisation sans facteurs carrés}
Soit $F$ un corps \emph{parfait} arbitraire. Nous nous intéressons dans ce
paragraphe à la façon de réduire le problème de la factorisation d'un
polynôme au problème de la factorisation d'un polynôme sans facteurs carrés.

Écrivons la factorisation en facteurs irréductibles d'un polynôme $f$ de
$F[x]$: $f=\prod_{i=1}^rf_i^{e_i}$, où les $f_i$ sont deux à deux non
associés et les $e_i$ strictement positifs. La partie sans facteurs carrés de
$f$ est égale à $\prod_{i=1}^rf_i$. De plus,
$$f'=\sum_{i=1}^re_i\frac f{f_i}f'_i.$$
Alors on peut voir que pour tout $i$, $f_i^{e_i-1}$ divise $f'$, et que de
plus, $f_i^{e_i}$ ne divise $f'$ que si $e_if'_i=0$. Ainsi, en
caractéristique nulle, la partie sans facteur carré de $f$ est $f/u$, où
$u=$pgcd$(f,f')$; en caractéristique $p$, ce quotient $f/u$ est égal à
$v=\prod_{p\nmid e_i}f_i$. Alors, $u/$pgcd$(u,v^n)=\prod_{p|e_i}f_i^{e_i}$.
On est donc ramené à calculer la racine $p^{\text{ème}}$ de ce polynôme, puis
à procéder de façon récursive.

\section{Algorithme de Berlekamp}
Ce dernier algorithme de factorisation utilise l'algèbre linéaire. Soit
$f\in\FM_q[x]$ un polynôme unitaire irréductible de degré $n>0$, et soit
$R=\FM_q[x]/(f)$. Alors $R$ est une $\FM_q$-algèbre de dimension $n$, et
l'application $\sigma$ de $R$ dans $R$ qui à $a$ associe $a^q$ est
$\FM_q$-linéaire. Soit $\beta=\sigma-\Id$. Alors $\beta$ est également
$\FM_q$-linéaire. On utilise l'isomorphisme d'algèbres
$$\chi \colon
R\longrightarrow\FM_q[x]/(f_1)\times\dots\times\FM_q[x]/(f_r)
 \simeq \FM_{q^{\deg f_1}} \times \dots\times\FM_{q^{\deg f_r}}.$$
Soit $\mathcal B=\Ker \beta$; $\chi(\mathcal B)$ est égal à
$\FM_q\times\dots\times\FM_q=\FM_q^r$ (c'est un abus de notation~: c'est en fait
égal au produit des images de $\FM_q$ dans $\FM_q[x]/(f_i)$).

Soit $Q$ la matrice de $\sigma$ dans la base de $R$ formée par les images de
$1,x,\dots,x^{n-1}$ dans $R$. L'algorithme de Berlekamp détermine dans un
premier temps une base de $\mathcal B$, en utilisant par exemple le pivot de
Gauss. Notons que $f$ est irréductible si et seulement si le rang de $Q-\Id $
est égal à $n-1$. 

On suppose à partir d'ici que $q$ est impair. Utilisant la base de
$\mathcal{B}$, on tire $b\in \mathcal{B}$ uniformément au hasard. On emploi
la même idée que pour la factorisation en degrés égaux. Si aucun $f_i$ ne
divise $b$, alors pour tout $i$, $b^{(q-1)/2}\equiv\pm1$ mod $f_i$, et
chacune des deux possibilités apparaît avec probabilité $1/2$, et ce de façon
indépendante pour tout $i$. L'algorithme suivant donne un facteur non trivial
de $f$, ou bien retourne «Échec»:
\begin{itemize}
\item On calcule $g_1=\pgcd(b,f)$. Si $g_1\ne1$, on retourne le facteur non
trivial $g_1$.

\item On calcule $a=b^{(q-1)/2}$.

\item On calcule $g_2=\pgcd(a-1,f)$. Si $g_2\ne1$ et $g_2\ne f$, alors on
retourne $g_2$, sinon, on retourne «Échec».
\end{itemize}

\begin{theo}
Cet algorithme répond «Échec» avec une probabilité inférieure à $1/2$, ou
sinon donne un facteur non trivial de $f$. Il utilise $O(n^3+n^2\log q)$
opérations dans $\FM_q$.
\end{theo}
\noindent Si l'on veut une factorisation complète de $f$, on se contente de
calculer une base de $\mathcal B$ une fois pour toute, puis on applique le
reste de l'algorithme récursivement à $g$ et $f/g$, où $g$ est le facteur
trouvé. Une analyse semblable à celle correspondant à l'algorithme de
factorisation en degrés égaux montre qu'on utilise en moyenne $O(n^3+n^2\log
q)$ opérations dans $\FM_q$.

\nocite{GatGer}
\bibliographystyle{kbplain}
\bibliography{kb}
\end{document}


