\documentclass[11pt]{amsart}
\usepackage{kb,a4wide}

\def\fb{\overline{f}}
\def\gb{\overline{g}}
\def\hb{\overline{h}}
\def\zb{\overline{z}}
\DeclareMathOperator{\pp}{pp}
\DeclareMathOperator{\cd}{cd}
\pagestyle{headings}

\begin{document}
\title{Algorithme d'Euclide modulaire sur les polynômes}
\maketitle

\section{Introduction}

Soient les polynômes
$$f(x)=824x^5-65x^4-814x^3-741x^2-979x-764$$
$$g(x)=216x^4+663x^3+880x^2-916x+617.$$
L'algorithme d'Euclide classique appliqué à $f$ et $g$, fait apparaître des
polynômes aux coefficients relativement grands. Ce fait n'est pas rare, et il y
a lieu de se demander dans quelle mesure la taille des coefficients pénalise
les performances de l'algorithme. En fait, une étude fine montre que
l'algorithme s'exécute tout de même en temps polynomial en la taille des
entrées.

Est-il possible de réduire, ou même éviter l'explosion des coefficients? On
peut tout d'abord exploiter le fait que le pgcd n'est défini qu'à une unité
multiplicative près, et n'utiliser par exemple que des polynômes unitaires.
C'est \textbf{l'algorithme d'Euclide unitaire}. On constate qu'avec cette
variante, la taille des coefficients est plus petite.

On peut aussi s'arranger pour n'avoir que des polynômes dans $\ZM[x]$, et donc
faire à chaque étape une pseudo-division, c'est-à-dire multiplier le dividende
par une puissance suffisante du coefficient dominant du diviseur. cela donne un
algorithme (\textbf{algorithme d'Euclide primitif}) au moins aussi performant
que l'algorithme unitaire.

\medskip

Une autre possibilité est la \emph{réduction modulo quelque chose}. Si comme
dans l'exemple proposé on travaille dans $\ZM[x]$, on peut réduire modulo un
nombre premier bien choisi, calculer le pgcd des polynômes réduits dans
$\FM_p[x]$ et relever le résultat dans $\ZM[x]$, si c'est possible.

Nous allons explorer ces diverses pistes.

\section{Variante «unitaire» de l'algorithme d'Euclide}

Dans cette variante de l'algorithme d'Euclide, on divise à chaque étape le
dernier reste par son coefficient dominant. Une analyse montre que cette
variante n'est, au moins asymptotiquement, pas plus couteuse en nombre
d'opérations sur le corps de base que l'algorithme classique.

Si on essaie le nouvel algorithme d'Euclide sur l'exemple de l'introduction,
les coefficients qui apparaissent sont moins gros que quand on utilise
l'algorithme classique. Et c'est ce qui se passe généralement, comme peut
l'indiquer l'exécution des deux algorithmes sur plusieurs couples de
polynômes choisis de façon aléatoire.

À titre de comparaison avec les algorithmes modulaires, indiquons le coût de
cet algorithme unitaire, sur $\QM[x]$.

\begin{theo}\label{cout_unitaire}
Soient $f$ et $g$ deux polynômes de $\ZM[x]$, de degrés respectifs $n$ et $m$,
dont tous les coefficients sont bornés par $A$ en valeur absolue, et soit
$\delta$ l'écart maximum de degrés entre deux restes successifs dans
l'algorithme d'Euclide unitaire appliqué à ces polynômes. Alors l'algorithme
utilise $O(n^3m\delta^2\log^2(nA))$ opérations sur les mots.
\end{theo}

\section{Borne de Mignotte}

Si l'on veut retrouver le pgcd de deux polynômes $f$ et $g$ de $\ZM[x]$,
connaissant le pgcd de leur réduction modulo un nombre premier $p$, il nous
faut bien choisir le nombre premier $p$. Pour cela, nous allons établir une
borne pour les coefficients de ce pgcd.

On définit la norme $2$ d'un polynôme $f=\sum_{i=0}^nf_ix^i$ de $\CM[x]$~:
$||f||_2=(\sum_{i=0}^n|f_i|^2)^{1/2}$. On veut trouver une borne $B$ pour la
norme d'un facteur de $f$, c'est-à-dire telle que pour tout facteur $h$ de
$f$, on ait $||h||_2\leq B$.

\begin{lemme}\label{lemme1}
Pour $f\in\CM[x]$ et $z\in\CM$, on a $||(x-z)f||_2=||(\zb x-1)f||_2$.
\end{lemme}

Écrivons
$$f=\sum_{i=0}^nf_ix^i=f_n\prod_{i=1}^n(x-z_i).$$
On définit $M(f)=|f_n|\prod_{i=1}^n$max$\{1,|z_i|\}$. Alors $M(f)\geq|\cd(f)|$
et $M(f)=M(g)M(h)$ si $f=gh$. Le théorème suivant permet d'estimer $M(f)$:

\begin{theo}[Landau]\label{landau}
Pour tout $f\in\CM[x]$, $M(f)\leq||f||_2$.
\end{theo}
\begin{proof}
On peut ordonner les racines de $f$ de façon que
$|z_1|,\dots,|z_k|>1$ et $|z_{k+1}|,\dots,|z_n|\leq1$. Alors $M(f)=|f_nz_1\dots
z_k|$. Soit
$$g=f_n\prod_{i=1}^k(\zb_ix-1)\prod_{i=k+1}^n(x-z_i).$$
Alors
$$M(f)^2=|f_n\zb_1\dots z_k|=|g_n|^2\leq||g||_2.$$
Pour finir, par utilisations successives du lemme~\ref{lemme1}, on trouve que
$||g||_2=||f||_2$.
\end{proof}

Pour la suite, on va également utiliser la norme $1$:
$||f||_1=\sum_{i=0}^n|f_i|$. Alors
$||f||_{\infty}\leq||f||_2\leq||f||_1\leq(n+1)||f||_{\infty}$.

\begin{theo}\label{h}
Soit $h=\sum_{i=0}^mh_ix^i\in\CM[x]$ de degré $m$ qui divise
$f=\sum_{i=0}^nf_ix^i\in\CM[x]$ de degré $n$. Alors
$$||h||_2\leq||h||_1\leq2^mM(h)\leq\left|\frac{h_m}{f_n}\right|2^mM(f)\leq\left|\frac{h_m}{f_n}\right|2^m||f||_2.$$
\end{theo}

\begin{proof}
La seconde inégalité vient de la règle de Viète décrivant les coefficients
d'un polynôme en fonction de ses racines. La quatrième utilise le
théorème~\ref{landau}.
\end{proof}

On en déduit alors la \textbf{borne de Mignotte}.

\begin{coro}\label{mignotte}
Soient $f$, $g$ et $h$ trois polynômes de $\ZM[x]$ de degrés respectifs $n$, $m$
et $k$, tels que $gh$ divise $f$ (dans $\ZM[x]$). Alors
\begin{itemize}
\item
  $||g||_{\infty}||h||_{\infty}
  \leq||g||_2||h||_2 \leq||g||_1||h||_1
  \leq 2^{m+k}||f||_2\leq(n+1)^{1/2}2^{m+k}||f||_{\infty}$.
\vskip 1mm

\item $||h||_{\infty}\leq||h||_2\leq2^{k}||f||_2\leq2^{m+k}||f||_1$ et
$||h||_{\infty}\leq||h||_2\leq(n+1)^{1/2}2^{k}||f||_{\infty}$.
\end{itemize}
\end{coro}

\section{Algorithme modulaire : version «grand nombre premier»}
On considère deux polynômes primitifs $f$ et $g$ de $\ZM[x]$. On va calculer
leur pgcd $h$ dans $\ZM[x]$, en utilisant un algorithme {\sl modulaire},
c'est-à-dire qu'on va réduire modulo un ou plusieurs nombres premiers.

Pour choisir ces nombres premiers, commençons par borner les coefficients du
pgcd $h$. Soit $A$ un majorant de $||f||_{\infty}$ et $||g||_{\infty}$. On
suppose que le degré $n$ de $f$ est supérieur ou égal au degré de $g$. Alors
$||h||_{\infty}\leq(n+1)^{1/2}2^nA$. On peut procéder de la façon suivante.

Soit $b$ le pgcd de $\cd(f)$ et $\cd(g)$. Soit $B=(n+1)^{1/2}2^nAb$. On choisit
un nombre premier $p \in [2B,4B]$ au hasard. Soient $\fb$ et $\gb$ les
réductions de $f$ et $g$ modulo $p$. On utilise l'algorithme d'Euclide pour
calculer le polynôme unitaire $v$ de $\ZM[x]$ tel que $||v||_{\infty}\leq p/2$
et tel que sa réduction podulo $p$ est le pgcd de $\fb$ et $\gb$. On calcule
ensuite $w$, $f^*$ et $g^*$ dans $\ZM[x]$ de norme infinie bornée par $p/2$ tels
que
\begin{equation}\label{relevement}
w\equiv bv \pmod{p}, \quad f^*w\equiv bf \pmod{p},\quad
g^*w\equiv bg \pmod{p}\,.
\end{equation}
Alors, si
\begin{equation}\label{condition}
||f^*||_1||w||_1 \leq  B \quad\text{et}\quad ||g^*||_1||w||_1\leq B
\end{equation}
le pgcd de $f$ et $g$ est égal à $\pp(w)$. Sinon, il faut recommencer avec un
autre nombre premier.

\begin{proof}
La condition~(\ref{condition}) est en fait nécessaire et suffisante.

En effet, si cette condition est vérifiée, alors $||f^*w||_{\infty}\leq p/2$.
Comme $||bf||_{\infty}\leq p/2$ et $f^*w\equiv bf$ mod $p$, on en déduit que
$f^*w=bf$. De même, $g^*w=bg$. Donc $w \mid \pgcd(bf,bg)$. Alors, un
raisonnement sur les degrés, et le fait que $\hb \mid \pgcd(\fb,\gb)$
montrent que $\pp(w)=\pgcd(f,g)$.

Réciproquement, si $\pp(w)=\pgcd(f,g)$, alors $w$ divise $bf$. D'après la
borne de Mignotte, $||bf/w||_{\infty}\leq B\leq p/2$. Donc $f^*=bf/w$ et de
même, $g^*=bg/w$. Donc, le corollaire~(\ref{mignotte}) montre que la
condition~(\ref{condition}) est vérifiée.
\end{proof}

\begin{theo}\label{cout_grand_premier}
L'algorithme précédent utilise $O(n^2(n^2+\log^2A))$ opérations sur les mots.
\end{theo}

Il reste le problème de trouver le nombre premier par lequel on va réduire. 

\begin{theo}\label{choix_premier}
Soit $r=\Res(f/h,g/h)$. L'entier $r$ est non nul, majoré en valeur absolue
par $(n+1)^nA^{2n}$. De plus, la condition~(\ref{condition}) est vraie si et
seulement si $p\nmid r$. Enfin, il existe un algorithme probabiliste
utilisant $O(n^3+\log^3A)$ opérations sur les mots, déterminant un entier $p$
entre $2B$ et $4B$ tel que $p$ est premier ne divisant pas $r$ avec
probabilité au moins $1/2$. La moyenne du nombre d'itérations nécessaires est
donc au plus $2$.
\end{theo}

\section{Algorithme modulaire : version «petits nombres premiers»}

On peut modifier cet algorithme en réduisant modulo plusieurs petits nombres
premiers, et en relevant les résultats par l'utilisation du théorème chinois.
On doit alors à chaque pas effectuer plusieurs fois l'algorithme d'Euclide,
mais les coefficients qui interviennent sont plus petits, ce qui diminue
considérablement le temps d'exécution pour de grandes valeurs des degrés et
des normes infinies des polynômes $f$ et $g$ de départ.

\bigskip

Soient deux polynômes primitifs $f$ et $g$ de $\ZM[x]$, tels que
$\deg(f)=n\geq\deg(g)$ et de norme infinie inférieure ou égale à $A$.

\medskip

On pose $b=\pgcd(\cd(f),\cd(g))$, $k=\ceil{2\log_2((n+1)^nbA^{2n})}$,
$B=(n+1)^{1/2}2^nAb$ et $L=\ceil{\log_2(2B+1)}$.

\medskip

On choisit un ensemble $S$ de $2L$ nombres premiers inférieurs à $2k\log k$,
et ne divisant pas~$b$. Pour chaque $p$ dans $S$, on calcule le polynôme
unitaire $v_p$ à coefficients dans $\{0,\dots,p-1\}$ dont la réduction modulo
$p$ est égale au pgcd des réductions $\fb$ et $\gb$ modulo $p$. Soit
$e=\min\set{\deg(v_p) \colon p\in S}$, on remplace $S\leftarrow\set{ p\in
S\colon \deg(v_p)=e}$. Si le cardinal $|S| \geq L$, alors on enlève $|S|-L$
éléments de $S$, sinon, on recommence avec un nouveau choix de $S$.

On calcule, grâce au théorème chinois, les polynômes $w$, $f^*$ et $g^*$ de
$\ZM[x]$ de norme infinie inférieure à $(\prod_{p\in S}p)/2$ tels que pour
tout $p\in S$
\begin{equation}\label{relevement2}
w\equiv bv_p \pmod{p},\quad f^*w\equiv bf \pmod{p},\quad g^*w\equiv
bg\pmod{p}\,.
\end{equation}
Alors si
\begin{equation}\label{condition2}
||f^*||_1||w||_1\leq B\quad\text{et}\quad ||g^*||_1||w||_1\leq B,
\end{equation}
on a $\pp(w)=\pgcd(f,g)$. Sinon, il faut recommencer.

\begin{theo}\label{cout_AEmod_petit}
L'algorithme utilise $O\big(n(n^2+\log^2A)(\log n+\log\log A)^2\big)$
opérations sur les mots.
\end{theo}

\bigskip

\noindent\textbf{Référence :}

Modern computer algebra, Joachim von zur Gathen, Jürgen Gerhard. Chapitre 6.

\end{document}
