\documentclass{article} \usepackage[french]{babel} \IfFileExists{TeXmacs.sty} {\usepackage{TeXmacs}} {\usepackage{/usr/share/TeXmacs-1.0.0.8/misc/latex/TeXmacs}} \newcommand{\chapter}[1]{\tmsection{\begin{center}\huge #1\end{center}}} \begin{document} \SelectFrench \title{Algorithmes de calcul de PGCD} \author{B. Parisse\\Institut Fourier\\UMR 5582 du CNRS \\Université de Grenoble I}\maketitle Comme on l'a remarqué dans le premier article, l'algorithme d'Euclide est inefficace pour calculer le pgcd de deux polynômes à coefficients entiers. On va présenter ici les algorithmes utilisés habituellement par les systèmes de calcul formel: sous-résultant (PRS), modulaire (GCDMOD), $p$-adique (EEZGD) et heuristique (GCDHEU). Le premier est une adaptation de l'algorithme d'Euclide et s'adapte à des coefficients assez génériques. Les trois autres ont en commun d'évaluer une ou plusieurs variables du polynôme (dans ce dernier cas il est nécessaire de bien distinguer le cas de polynômes à plusieurs variables) et de reconstruire le pgcd par des techniques distinctes, la plupart du temps ces algorithmes fonctionnent seulement si les coefficients sont entiers. Soit $\tmop{donc} P$ et $Q$ deux polynômes à coefficients dans un corps. Le pgcd de $P$ et $Q$ n'est défini qu'à une constante près. Mais lorsque les coefficients de $P$ et $Q$ sont dans un anneau euclidien comme par exemple $\mathbb{\mathbb{\mathbb{\mathbb{\text{$\mathbb{Z}$}}}}}$ ou $\text{$\mathbb{Z}$} [ i ]$, on appelle pgcd de $P$ et $Q$ un polynôme $D$ tel que $P / D$ et $Q / D$ soient encore à coefficients dans l'anneau, et que $D$ soit optimal, c'est-à-dire que si un multiple $\mu D$ de $D$ vérifie $P / \mu D$ et $Q / \mu D$ sont à coefficients dans l'anneau, alors $\mu$ est inversible. La première étape d'un algorithme de calcul de pgcd consiste donc à diviser par le pgcd des coefficients entiers de chaque polynôme. {\tmstrong{Exemple}}: $P = 4 X^2 - 4$ et $Q = 6 X^2 + 12 X + 6$. Le polynôme $X + 1$ est un pgcd de $P$ et $Q$ puisqu'il est de degré maximal divisant $P$ et $Q$ mais le pgcd de $P$ et $Q$ est $2 ( X + 1 )$. Remarquons qu'avec notre définition $- 2 ( X + 1 )$ convient aussi. Par convention on appelera pgcd le polynôme ayant un coefficient dominant positif. {\tmstrong{Définition}}: On appelle contenu $c ( P )$ d'un polynôme $P$ le pgcd des coefficients de $P$. On définit alors la partie primitive de $P$: $\tmop{pp} ( P ) = P / c ( P )$. Si $c(P)=1$, on dit que $P$ est primitif. On montre que~: \[ D = \tmop{pgcd} ( P, Q ) = \tmop{pgcd} ( c ( P ), c ( Q )) \tmop{pgcd} ( \tmop{pp} ( P ), \tmop{pp} ( Q )) \] \section{Le sous-résultant.} La première idée qui vient à l'esprit pour améliorer l'efficacité de l'algorithme d'Euclide consiste à éviter les fractions qui sont créées par les divisions euclidiennes. On utilise à cet effet la pseudo-division: au lieu de prendre le reste $R$ de la division euclidienne du polynôme $P$ par $Q$, on prend le reste de la division de $P q^{\delta + 1}$ par $Q$, où $q$ désigne le coefficient dominant de $Q$ et $\delta$ la différence entre le degré de $P$ et de $Q$. {\tmstrong{Exercice:}} En utilisant votre système de calcul formel préféré, calculez les restes intermédiaires générés dans l'algorithme d'Euclide lorsqu'on utilise la pseudo-division par exemple pour les polynômes $P ( x ) = ( x + 1 )^7 - ( x - 1 )^6$ et sa dérivée. {\tmstrong{Une solution avec giac/xcas}}: \begin{verbatim} // -*- mode:C++ -*- a,b 2 polynomes -> pgcd de a et b pgcd(a,b):={ local P,p,Q,q,R,g,h,d; // convertit a et b en polynomes listes et extrait la partie primitive P:=symb2poly1(a); p:=lgcd(P); // pgcd des elements de la liste P:=P/p; Q:=symb2poly1(b); q:=lgcd(Q); Q:=Q/q; if (size(P) \left( \frac{| z |}{2} \right)^n \] qui contredit notre majoration de $| C ( z ) |$. \begin{theorem} Soit $P$ et Q deux polynômes à coefficients entiers. On choisit un entier z tel que $| z | \geqslant 2 \min ( | P |, | Q | ) + 2$, si la partie primitive du polynôme $G$ reconstruit à partir du pgcd de $P ( z ) \tmop{et}$Q(z) par écriture en base $z$ (avec comme reste euclidien le reste symétrique) divise $P$ et $Q$ alors c'est le pgcd de $P$ et $Q$. \end{theorem} Pour finir la démonstration du théorème, il nous faut encore montrer le lemme. On a \[ - a_n x^n = a_{n - 1} x^{n - 1} + \ldots . + a_0 \] Donc \[ | a_n | | x |^n \leqslant | P | ( 1 + \ldots . + | x |^{n - 1} ) = | P | \frac{| x |^n - 1}{| x | - 1} \] Ici on peut supposer que $| x | \geqslant 1$, sinon le lemme est démontré, donc $| x | - 1$ est positif et \[ | a_n | ( | x | - 1 ) \leqslant | P | \frac{| x |^n - 1}{| x |^n} \Rightarrow | x | - 1 < \frac{| P |}{| a_n |} \] Remarques \begin{itemize} \item Le théorème publié par Char, Geddes et Gonnet porte sur des coefficients entiers et c'est comme cela qu'il est utilisé par les systèmes de calcul formel (en commençant historiquement par Maple). Peu de systèmes l'utilisent pour les polynômes à coefficients entiers de Gauss. On peut d'ailleurs généraliser le théorème à d'autres types de coefficients, à condition d'avoir un anneau euclidien plongé dans $\mathbb{C}$ avec une minoration sur la valeur absolue des élements non nuls de l'anneau. \item Nous n'avons jusqu'à présent aucune certitude qu'il existe des entiers $z$ tels que la partie primitive de $G$ divise $P$ et $Q$. Nous allons montrer en utilisant l'identité de Bézout que pour $z$ assez grand c'est toujours le cas. Plus précisément, on sait qu'il existe deux polynômes $U$ et $V$ tels que \[ P U + Q V = D \] Attention toutefois, $U$ et $V$ sont à coefficients rationnels, pour avoir des coefficients entiers, on doit multiplier par une constante entière $\alpha$, donc en évaluant en $z$ on obtient l'existence d'une égalité à coefficients entiers \[ P ( z ) u + Q ( z ) v = \alpha D ( z ) \] Donc le pgcd $g$ de $P ( z )$ et $Q ( z )$ divise $\alpha D ( z ) = \alpha d$. Comme $g$ est un multiple de $d$, on en déduit que $g = \beta d$, où $\beta$ est un diviseur de $\alpha$. Si on a choisi $z$ tel que \[ | z | > \text{ $2 | D | | \alpha |$} \] alors $| z | > 2 | D | | \beta |$ donc l'écriture symétrique en base $z$ de $g$ est $G = \beta D$. Donc la partie primitive de $G$ est $D$, le pgcd de $P$ et $Q$. \end{itemize} \begin{example} Si $P_0 = 6 ( X^2 - 1 )$ et $Q_0 = 4 ( X^3 - 1 )$. Le contenu de $P_0$ est 6, celui de $Q_0$ est 4.\\ On a donc pgcd des contenus = 2, $P = X^2 - 1, Q = X^3 - 1$. La valeur initiale de $z$ est donc $2 \ast 1 + 2 = 4$. On trouve $P ( 4 ) = 15, Q ( 4 ) = 63$. Le pgcd entier de 15 et 63 est 3 que nous écrivons symétriquement en base 4 sous la forme $3 = 1 \ast 4 - 1$, donc $G = X - 1$, sa partie primitive est $X - 1$. On teste si $X - 1$ divise $P$ et $Q$, c'est le cas, donc c'est le pgcd de $P$ et $Q$ et le pgcd de $P_0$ et $Q_0$ est $2 ( X - 1 )$. \end{example} {\bf Algorithme gcdheu}\\ En arguments deux polynômes $P_0$ et $Q_0$ à coefficients entiers ou entiers de Gauss. Retourne le pgcd de $P_0$ et $Q_0$ ou faux en cas d'échec. \begin{enumerate} \item Calculer le contenu de $P_0$ et $Q_0$. Vérifier que les coefficients sont entiers de Gauss sinon retourner faux. \item Extraire la partie primitive $P$ de $P_0$ et $Q$ de $Q_0$, calculer le pgcd $c$ des contenus de $P_0$ et $Q_0$ \item Déterminer $z = 2 \min ( | P |, | Q | ) + 2$. \item Début de boucle: initialisation du nombre d'essais à 1, test d'arrêt sur un nombre maximal d'essais, avec changement de $z$ entre deux itérations (par exemple $z \assign 2 z$). \item Calculer le pgcd $g$ de $P ( z )$ et $Q ( z )$ puis son écriture symétrique en base $z$ dont on extrait la partie primitive $G$. \item Si $G \tmop{ne} \tmop{divise} \tmop{pas}$$P$ passer à l'itération suivante. De même pour $Q$. \item Retourner $c G$ \item Fin de la boucle \item Retourner faux. \end{enumerate} On remarque au passage qu'on a calculé le quotient de $P$ par $G$ et le quotient de $Q$ par $G$ lorsque la procédure réussit. On peut donc passer à la procédure gcdheu deux paramètres supplémentaires par référence, les deux polynômes que l'on affectera en cas de succès, ce qui optimise la simplification d'une fraction de 2 polynômes. \subsection{Le pgcd modulaire} On part du fait que si $D$ est le pgcd de $P$ et $Q$ dans $\mathbb{Z}$ (ou $\mathbb{Z} [ i ] )$ alors après réduction modulo un nombre premier $n$ qui ne divise pas les coefficients dominants de $P$ et $Q$, $D$ divise le pgcd $G$ de $P$ et $Q$ dans $\mathbb{Z} / n \mathbb{Z}$ (par convention, le pgcd dans $\mathbb{Z} / n \mathbb{Z}$ est normalisé pour que son coefficient dominant vaille 1). Comme on calcule $G$ dans $\mathbb{Z} / n \mathbb{Z}$, les coefficients des restes intermédiaires de l'algorithme d'Euclide sont bornés, on évite ainsi la croissance exponentielle des coefficients. Il faudra ensuite reconstruire $D$ à partir de $G$. On remarque d'abord que si on trouve $G = 1,$ alors $P$ et $Q$ sont premiers entre eux. En général, on peut seulement dire que le degré de $G$ est supérieur ou égal au degré de $D$. En fait, le degré de $G$ est égal au degré de $D$ lorsque les restes de l'algorithme d'Euclide (calculé en effectuant des pseudo-divisions, cf. l'exercice 1) ont leur coefficient dominant non divisible par $n$. Donc plus $n$ est grand, plus la probabilité est grande de trouver $G$ du bon degré. Dans la suite, nous allons déterminer une borne $b$ à priori majorant les coefficients de $D$. On utilisera ensuite la même méthode que dans l'algorithme modulaire de recherche de racines évidentes: on multiplie $G$ dans $\mathbb{Z} / n \mathbb{Z}$ par le pgcd dans $\mathbb{Z}$ des coefficients dominants $p$ et $q$ de $P$ et $Q$. Soit $\tilde{D} = \tmop{pgcd} ( p, q ) G$ le résultat écrit en représentation symétrique. Si $n \geqslant b \tmop{pgcd} ( p, q )$ et si $G$ est du bon degré, on montre de la même manière que $D = \tilde{D}$. Comme on ne connait pas le degré de $D$, on est obligé de tester si $\tilde{D}$ divise $P$ et $Q$. Si c'est le cas, alors $\tilde{D}$ divise $D$ donc $\tilde{D} = D$ puisque $\tmop{degre} ( \tilde{D} ) = \tmop{degre} ( G ) \geqslant \tmop{degre} ( D )$. Sinon, $n$ est un nombre premier malchanceux pour ce calcul de pgcd ($\tmop{degre} ( G ) \geqslant \tmop{degre} ( D )$), il faut essayer un autre premier. {\tmstrong{Remarque:}} On serait tenté de dire que les coefficients de $D$ sont bornés par le plus grand coefficient de $P$. C'est malheureusement faux, par exemple $( X + 1 )^2$ dont le plus grand coefficient est 2 divise $( X + 1 )^2 ( X - 1 )$ dont le plus grand coefficient (en valeur absolue) est 1. Soit $P = \sum p_i X^i$ un polynôme à coefficients entiers. On utilise la norme euclidienne \begin{equation} | P |^2 = \sum | p_i |^2 \end{equation} On établit d'abord une majoration du produit des racines de norme supérieure à 1 de $P$ à l'aide de $| P |^{}$. Ensuite si $D$ est un diviseur de $P$, le coefficient dominant $d$ de $D$ divise le coefficient dominant $p$ de $P$ et les racines de $D$ sont aussi des racines de $P$. On pourra donc déterminer une majoration des polynômes symétriques des racines de $D$ et donc des coefficients de $D$. \begin{lemma} \label{lemme:A} Soit $A = \sum_{j = 0}^a a_j X^j$ un polynôme et $\alpha \in \mathbb{C}$. Alors \[ \text{$| ( X - \alpha ) A | = | ( \overline{\alpha} X - 1 ) A |$} \] \end{lemma} Pour prouver le lemme \ref{lemme:A}, on développe les produits de polynômes. On pose $a_{-1} = a_{a + 1} = 0$ et on note $\Re$ la partie réelle. \[ \text{$| ( X - \alpha ) A |^2 = \sum_{j = 0}^{a + 1}$} | a_{j - 1} - \alpha a_j |^2 = \sum_{j = 0}^{a + 1} | a_{j - 1} |^2 + | \alpha |^2 | a_j |^2 - 2 \Re ( a_{j - 1} \overline{\alpha a_j} ) \] \[ \text{$| ( \overline{\alpha} X - 1 ) A |$}^2 = \sum_{j = 0}^{a + 1} | \overline{\alpha} a_{j - 1} - a_j |^2 = \sum_{j = 0}^{a + 1} | \alpha |^2 | a_{j - 1} |^2 + | a_j |^2 - 2 \Re ( \overline{\alpha} a_{j - 1} \overline{a_j} ) \] Les deux donnent bien le même résultat. Soit $P ( X ) = p \prod ( X - \alpha_j )$ la factorisation de $P$ sur $\mathbb{C}$. On introduit le polynôme \[ \tilde{P} = p \prod_{j / | \alpha_j | \geqslant 1} ( X - \alpha_j ) \prod_{j / | \alpha_j | < 1} ( \overline{\alpha_j} X - 1 ) \] qui d'après le lemme a la même norme que $P$. La norme de $P$ majore donc le coefficient constant de $\tilde{P} $ d'où: \begin{equation} \label{mignotte} \text{$ \prod_{j / | \alpha_j | \geqslant 1} | \alpha_j | \leqslant \frac{| P |}{| p |}$} \end{equation} On remarque que (\ref{mignotte}) reste vraie si on considère les racines $\delta_j$ de norme plus grande que 1 d'un diviseur $D$ de $P$ puisque le produit porte alors sur un sous-ensemble. On écrit maintenant l'expression des coefficients $d_j$ de $D$ à l'aide des racines $\delta_j$ de $D$: \[ | d_{m - j} | = | d | \left| \sum_{\tmop{choix} \tmop{de} j \tmop{racines} \tmop{parmi} \tmop{les} m \tmop{racines} \tmop{de} D} \quad \prod_{\delta_k \in \tmop{racines} \tmop{choisies}} \delta_k \right| \] Pour majorer $| d_{m - j} |$, on commence par majorer $| \delta_k |$ par $\beta_k = \max ( 1, | \delta_k | )$. On est donc ramené à majorer \[ \sigma_{j, m} ( \beta ) = \sum_{\tmop{choix} \tmop{de} j \tmop{parmi} m \tmop{valeurs} \beta_k} \quad \prod_{\beta_k \in \tmop{choix}} \beta_k \] avec pour hypothèse une majoration de $M = \prod_{k = 1}^m \beta_k$ donnée par la relation (\ref{mignotte}). Pour cela, on cherche le maximum de $\sigma_{j, m} ( \beta )$ sous les contraintes $M$ fixé et $\beta_k \geqslant 1$. On va montrer que le maximum ne peut être atteint que si l'un des $\beta_k = M$ (et tous les autres $\beta_k = 1 )$. Sinon, quitte à réordonner supposons que les $\beta_k$ sont classés par ordre croissant. On a donc $\beta_{m - 1} \neq 1$, on pose $\widetilde{\beta_k} = \beta_k$ pour $k \leqslant m - 2$, $\tilde{\beta}_{m - 1} = 1$ et $\tilde{\beta}_m = \beta_{m - 1} \beta_m$. Comparons $\sigma_{j, m} ( \beta )$ et $\sigma_{j, \tmop{nm}} ( \tilde{\beta} )$. Si le choix de $j$ parmi $m$ comporte $k = m - 1$ et $k = m$, le produit est inchangé. Sinon on a la somme de deux produits, l'un contenant $k = m - 1$ et l'autre $k = m$. On compare donc $B ( \beta_{m - 1} + \beta_m )$ et $B ( 1 + \beta_{m - 1} \beta_m )$ avec $B = \prod_{\beta_k \in \tmop{reste} \tmop{du} \tmop{choix}} \beta_k$. Comme \[ \text{$1 + \beta_{m - 1} \beta_m \geqslant \beta_{m - 1} + \beta_m$} \] puisque la différence est le produit $(1-\beta_m)(1-\beta_{m-1})$ de deux nombres positifs, on arrive à la contradiction souhaitée. Ensuite on décompose les choix de $\sigma_{m, j}$ en ceux contenant $M$ et des 1 et ceux ne contenant que des 1, d'où la majoration \[ \sigma_{j, m} ( \beta ) \leqslant \left(\begin{array}{c} m - 1\\ j - 1 \end{array}\right) M + \left(\begin{array}{c} m - 1\\ j \end{array}\right) \] et finalement \begin{equation} | d_{m - j} | \leqslant | d | \left( \left(\begin{array}{c} m - 1\\ j - 1 \end{array}\right) \frac{| P |}{| p |} + \left(\begin{array}{c} m - 1\\ j \end{array}\right) \right) \label{pgcdd} \end{equation} On peut en déduire une majoration indépendante de $j$ sur les coefficients de $D$, en majorant $| d |$ par $| p |$ (puisque $d$ divise $p$) et les coefficients binomiaux par $2^{m - 1}$ (obtenue en développant $( 1 + 1 )^{m - 1}$). D'où le \begin{theorem} (Landau-Mignotte) Soit $P$ un polynôme à coefficients entiers (ou entiers de Gauss) et $D$ un diviseur de $P$ de degré $m$. Si $| P |$ désigne la norme euclidienne du vecteur des coefficients de $P$ et $p$ le coefficient dominant de $P$ alors les coefficients $d_j$ de $D$ satisfont l'inégalité \begin{equation} | d_j | \leqslant 2^{m - 1} ( | P | + | p | ) \end{equation} \end{theorem} Avec cette estimation, on en déduit que si $n$ est un premier plus grand que \begin{equation} \text{$\min \left( 2^{\tmop{degre} ( P ) - 1} ( | P | + | p | ), 2^{\tmop{degre} ( Q ) - 1} ( | Q | + | q | ) \right)$}, \label{pgcdbound} \end{equation} alors le pgcd trouvé dans $\mathbb{Z} / n \mathbb{Z}$ va se reconstruire en un pgcd dans $\mathbb{Z}$ si son degré est le bon. Malheureusement la borne précédente est souvent très grande par rapport aux coefficients du pgcd et calculer dans $\mathbb{Z} / n \mathbb{Z}$ s'avèrera encore inefficace (surtout si le pgcd est 1). Cela reste vrai même si on optimise un peu la majoration (\ref{pgcdbound}) en repartant de (\ref{pgcdd}). L'idée est donc de travailler modulo plusieurs nombres premiers plus petits et reconstruire le pgcd des 2 polynômes à coefficients entiers à partir des pgcd des polynômes dans $\text{$\mathbb{Z}$} / n \text{$\mathbb{Z}$}$ et du théorème des restes chinois. En pratique on prend des nombres premiers inférieurs à la racine carrée du plus grand entier hardware de la machine (donc plus petits que $2^{16}$ sur une machine 32 bits) ce qui permet d'utiliser l'arithmétique hardware du processeur sans risque de débordement. {\tmstrong{Algorithme du PGCD modulaire en 1 variable:}} En argument: 2 polynômes primitifs $P$ et $Q$ à coefficients entiers. Le résultat renvoyé sera le polynôme pgcd. Variable auxiliaire: un entier $N$ initialisé à 1 qui représente le produit des nombres premiers utilisés jusqu'ici et un polynôme $H$ initialisé à 0 qui représente le pgcd dans $\mathbb{Z} / N \mathbb{Z}$. Boucle infinie : \begin{enumerate} \item Chercher un nouveau nombre premier $n$ qui ne divise pas les coefficients dominants $p$ et $q$ de $P$ et $Q$ \item Calculer le pgcd $G$ de $P$ et $Q$ dans $\mathbb{Z} / n \mathbb{Z}$. Si $G$=1, renvoyer 1. \item Si $H = 0$ ou si le degré de $G$ est plus petit que le degré de $H$, recopier $G$ dans $H$ et $n$ dans $N$, passer à la 6ème étape \item Si le degré de $G$ est plus grand que celui de $H$ passer à l'itération suivante \item Si le degré de $G$ est égal au degré de $H$, en utilisant le théorème des restes chinois, calculer un polynôme $\tilde{H}$ tel que $\tilde{H} = H$ modulo $N$ et $\tilde{H} = G$ modulo $n$. Recopier $\tilde{H}$ dans $H$ et $n N$ dans $N$. \item Ecrire $\tmop{pgcd} ( p, q ) H$ en représentation symétrique. Soit $\tilde{H}$ le résultat rendu primitif. Tester si $\tilde{H}$ divise $P$ et $Q$. Si c'est le cas, renvoyer $\tilde{H}$, sinon passer à l'itération suivante. \end{enumerate} Finalement on n'a pas utilisé $b$, la borne de Landau-Mignotte. On peut penser que l'étape 6 ne devrait être effectuée que lorsque $N$ est plus grand que $\tmop{pgcd} ( p, q ) b$. En pratique, on effectue le test de l'étape 6 plus tôt parce que les coefficients du pgcd sont rarement aussi grand que $b$. Mais pour éviter de faire le test trop tôt, on introduit une variable auxiliaire $H'$ qui contient la valeur de $H$ de l'itération précédente et on ne fait le test que si $H' = H$ (ou bien sûr si on a dépassé la borne). {\tmstrong{Remarque}}: L'algorithme ci-dessus fonctionne également pour des polynômes à plusieurs variables. {\tmstrong{Exemple 1:}} Calcul du pgcd de $( X + 1 )^3 ( X - 1 )^4$ et $( X^4 - 1 )^{}$. Prenons pour commencer $n = 2$. On trouve comme pgcd $X^4 + 1$ (en effet $- 1 = 1$ donc on cherchait le pgcd de $( X + 1 )^7$ et de $X^4 + 1 = ( X + 1 )^4$). On teste si $X^4 + 1$ divise $P$ et $Q$, ce n'est pas le cas donc on passe au nombre premier suivant. Pour $n = 3$, on trouve $X^2 - 1$. Donc $n = 2$ n'était pas un bon nombre premier pour ce calcul de pgcd puisqu'on a trouvé un pgcd de degré plus petit. On teste si $X^2 - 1$ divise $P$ et $Q$, c'est le cas ici donc on peut arrêter, le pgcd cherché est $X^2-1$. {\bf{Exemple} 2 :} Calcul du pgcd de $( X + 1 )^3 ( X - 1 )^4$ et $( X^4 - 1 )^3$. Pour $n = 2$, on trouve un polynôme de degré 7. Pour $n = 3$, on trouve $X^6 - 1$ donc $n = 2$ était une mauvaise réduction. Comme $X^6 - 1$ ne divise pas $P$ et $Q$, on passe à $n = 5$. On trouve $X^6 + 2 X^4 - 2 X^2 - 1$. On applique le théorème des restes chinois qui va nous donner un polynôme dans $\mathbb{Z} / 15 \mathbb{Z}$. On cherche donc un entier congru à 2 modulo 5 et à 0 modulo 3, -3 est la solution (écrite en représentation symétrique), donc le polynôme modulo 15 est $X^6 - 3 X^4 + 3 X^2 - 1 = ( X^2 - 1 )^3$. Ce polynôme divise $P$ et $Q$, c'est donc le pgcd de $P$ et de $Q$. \section{Le pgcd à plusieurs variables.} \subsection{Le pgcd heuristique.} On suppose comme dans le cas à une variable que les polynômes sont primitifs, donc qu'on a simplifié les polynômes par le pgcd entier de leurs coefficients entiers. Le principe est identique à celui du PGCD à 1 variable, on évalue les deux polynômes $P$ et $Q$ de $k$ variables $X_1, \ldots ., X_k$ en un $X_k = z$ et on calcule le pgcd $g$ des 2 polynômes $P ( z )$ et $Q ( z )$ de $k - 1$ variables. On remonte ensuite à un polynôme $G$ par écriture symétrique en base $z$ de $g$ et on teste si $\tmop{pp} ( G )$ divise $P$ et $Q$. Il s'agit à nouveau de montrer que si $z$ est assez grand, alors $\tmop{pp} ( G )$ est le pgcd cherché. On sait que $d = D ( z )$ divise $g$. Il existe donc un polynôme $a$ de $k - 1$ variables tel que $g = a d$. On sait aussi que $\tmop{pp} ( G )$ divise $D$, donc il existe un polynôme $C$ de $k$ variables tel que $D = C \ast \tmop{pp} ( G ) .$ On évalue en $z$ et on obtient $d = C ( z ) g / c ( G )$, où $c ( G )$ est un entier, donc \[ c ( G ) = a \ast C ( z ) \] Comme $c ( G )$ est un entier, $a$ et $C ( z )$ sont des polynômes constants. Comme précédemment, on a aussi $| C ( z ) | \leqslant | z | / 2$ puisque $| c ( G ) | \leqslant | z | / 2$. \begin{itemize} \item Premier cas: si $C$ ne dépend que de la variable $X_k$. On continue le raisonnement comme dans le cas unidimensionnel. \item Deuxième cas: si $C$ dépend d'une autre variable, par exemple $X_1$. On regarde le coefficient de plus haut degre de $C$ par rapport a $X_1$. Ce coefficient divise le coefficient de plus haut degre de $P$ et de $Q$ par rapport a $X_1$. Comme $C ( z )$ est constant, on en deduit que le coefficient de plus haut degre de $P$ et $Q$ par rapport a $X_1$ est divisible par $X_k - z$ donc le coefficient de plus bas degre en $X_k$ de ces coefficients de plus haut degre est divisible par $z$, ce qui contredit la majoration de ce coefficient. \end{itemize} En pratique, cet algorithme nécessite le calcul récursif de pgcd sans garantie de réussite. On l'évite donc s'il y a beaucoup de variables (la limite est par exemple de 5 pour MuPAD). \subsection{Le pgcd modulaire multivariables.} Ici, on travaille modulo $X_n - \alpha_{}$, où $X_1, \ldots ., X_n$ désignent les variables des polynômes. On considère donc deux polynômes $P$ et $Q$ comme polynômes de la variables $X_n$ avec des coefficients dans $\mathbb{Z} [ X_1, \ldots ., X_{n - 1} ]$. On évalue en $X_n = \alpha$, on obtient deux polynômes en $n - 1$ variables dont on calcule le pgcd (récursivement). Il s'agit de reconstruire le pgcd par interpolation. Tout d'abord, on a une borne évidente sur le degré du pgcd par rapport à la variable $X_n$, c'est le minimum $\delta$ des degrés par rapport à $X_n$ des polynômes $P$ et $Q$. A première vue, il suffit donc d'évaluer les polynômes en $\delta + 1$ points $\alpha$. Il faut toutefois prendre garde aux mauvaises évaluations et à la normalisation des pgcd avant d'interpoler. En effet, si $D ( X_1, \ldots ., X_n )$ désigne le pgcd de $P$ et $Q$ et $G ( X_1, \ldots ., X_{n - 1} )$ le pgcd de $P ( X_1, \ldots ., X_{n - 1}, \alpha )$ et de $Q ( X_1, \ldots ., X_{n - 1}, \alpha )$, on peut seulement dire $D ( X_1, \ldots ., X_{n - 1}, \alpha )$ divise $G$. Plusieurs cas sont donc possibles lorsqu'on évalue en un nouveau point $\alpha$: \begin{itemize} \item l'un des degrés de $G$ est plus petit que le degré du polynôme $D'$ reconstruit par interpolation jusque là. Dans ce cas, toutes les évaluations qui ont conduit à reconstruire $D'$ étaient mauvaises. Il faut recommencer l'interpolation à zéro ou à partir de $G$ (si tous les degrés de $G$ sont inférieurs ou égaux aux degrés du $D'$ reconstruit). \item l'un des degrés de $G$ est plus grand que le degré du $D'$ reconstruit jusque là. Il faut alors ignorer $\alpha$. \item Tous les degrés de $G$ sont égaux aux degrés du $D'$ reconstruit jusque là. Dans ce cas, $G$ est un multiple entier du polynôme $D'$ reconstruit jusque là et évalué en $X_n = \alpha$. Si on suppose qu'on a pu s'arranger pour que ce multiple soit 1, on ajoute le point $\alpha$ aux points d'évaluation précédents $\alpha_j$ en posant: \[ D' = D' + ( G - D' ) \frac{\prod_{\alpha_j} ( X_n - \alpha_j )}{\prod_{\alpha_j} ( \alpha - \alpha_j )} \] \end{itemize} On voit que les mauvaises évaluations se détectent simplement par les degrés. Pour la normalisation, on utilise une petite astuce: au lieu de reconstruire $\tmop{le} \tmop{pgcd} D$, on va reconstruire un multiple du pgcd $D$ (ce multiple appartiendra à $\mathbb{Z} [ X_n ] )$. On voit maintenant $P$ et $Q$ comme des polynômes en $n - 1$ variables $X_1, \ldots ., X_{n - 1}$ à coefficients dans $\mathbb{Z} [ X_n ]$. Alors lcoeff$(D)$, le coefficient dominant de $D$ (relativement à l'ordre lexicographique sur les variables $X_1,...,X_{n-1}$), est un polynôme en $X_n$ qui divise le coefficient dominant de $P$ et de $Q$ donc divise le coefficient dominant du pgcd des coefficients dominants de $P$ et de $Q$. On va donc reconstruire le polynôme~: \[ D' = D \frac{\Delta ( X_n )}{\tmop{lcoeff} ( D ) ( X_n )}, \Delta ( X_n ) = \tmop{pgcd} ( \tmop{lcoeff} ( P ) ( X_n ), \tmop{lcoeff} ( Q ) ( X_n )) \] c'est-à-dire $D$ multiplié par un polynôme qui ne dépend que de $X_n$. Revenons à $G$ en un point $\alpha$ de bonne évaluation. C'est un multiple entier de $D ( X_1, \ldots ., X_{n - 1}, \alpha )$: \[ G = \beta D ( X_1, \ldots ., X_{n - 1}, \alpha ) \] Donc, comme polynômes de $X_1,...,X_{n-1}$ à coefficients dans $\mathbb{Z}[X_n]$ ou dans $\mathbb{Z}$, $\tmop{lcoeff} ( G ) = \beta \tmop{lcoeff} ( D )_{| X_n = \alpha}$. Comme $\tmop{lcoeff} ( D )$ divise $\Delta ( X_n )$, il en est de même en $X_n = \alpha$ donc lcoeff$(G)$ divise $\beta \Delta(\alpha)$. On en déduit que $ \Delta ( \alpha) G$ qui est divisible par $ \Delta (\alpha) \beta$ est divisible par $\tmop{lcoeff} ( G )$. On va donc considérer le polynôme $ \Delta (\alpha) G / \tmop{lcoeff} ( G )$ : ses coefficients sont entiers et son coefficient dominant est $$\Delta ( \alpha) = \mbox{lcoeff}(D'( X_1, \ldots ., X_{n - 1}, \alpha ))$$ donc \[ \Delta (\alpha) G / \tmop{lcoeff} ( G )= D'( X_1, \ldots ., X_{n - 1}, \alpha )\] {\tmstrong{Algorithme du pgcd modulaire à plusieurs variables (interpolation dense)}}: Arguments: 2 polynômes primitifs $P$ et $Q$ de $n$ variables $X_1, \ldots ., X_n$ à coefficients entiers. Renvoie le pgcd de $P$ et $Q$. \begin{enumerate} \item Si $n = 1$, renvoyer le pgcd de $P$ et $Q$ en une variable. \item Test rapide de pgcd trivial par rapport à $X_n$. On cherche des $n - 1$-uplets $\alpha$ tels que $P ( \alpha, X_n )$ et $Q ( \alpha, X_n )$ soient de même degré que $P$ et $Q$ par rapport à la variable $X_n$. On calcule le pgcd $G$ de ces 2 polynômes en une variable. Si le pgcd est constant, alors on retourne le pgcd des coefficients de $P$ et $Q$. \item On divise $P$ et $Q$ par leur contenu respectifs vu comme polynômes en $X_1, \ldots ., X_{n - 1}$ à coefficients dans $\mathbb{Z} [ X_n ]$, on note $C ( X_n )$ le pgcd des contenus. On calcule aussi le pgcd $\Delta ( X_n )$ des coefficients dominants de $P$ et de $Q$. \item On initialise $D'$ le pgcd reconstruit à 0, $I ( X_n )$ le polynôme d'interpolation à 1, $\delta=(\delta_1,...,\delta_{n-1})$ la liste des degrés partiels du pgcd par rapport à $X_1, \ldots ., X_{n - 1}$ au minimum des degrés partiels de $P$ et $Q$ par rapport à $X_1, \ldots ., X_{n - 1}$, $e$ le nombre d'évaluation à 0 et $E$ l'ensemble des points d'interpolation à la liste vide. \item Boucle infinie: \begin{itemize} \item Faire $\alpha$=entier aléatoire n'appartenant pas à $E$ jusqu'à ce que \begin{eqnarray*} \text{degre($P ( X_1, \ldots ., X_{n - 1}, \alpha ))$=$\tmop{degre}_{X_n} ( P ( X_1, \ldots ., X_n )$} & & \\ \tmop{degre} ( Q ( X_1, \ldots ., X_{n - 1}, \alpha )) = \tmop{degre}_{X_n} ( Q ( X_1, \ldots ., X_n )) & & \end{eqnarray*} \item Calculer le pgcd $G ( X_1, \ldots ., X_{n - 1} )$ en $n - 1$ variables de $P ( X_1, \ldots ., X_{n - 1}, \alpha )$ et $Q ( X_1, \ldots ., X_{n - 1}, \alpha )$. \item Si $\tmop{degre}_{} ( G )_i < \delta_i$ pour un indice au moins. Si $\tmop{degre} ( G ) \leqslant \delta$, on pose $\delta = \tmop{degre} ( G )$, $D' = G \frac{\Delta ( \alpha )}{\tmop{lcoeff} ( G )}$, $I = X_n - \alpha$, $e = 1$ et $E = [ \alpha ]$, sinon on pose $\delta = \min ( \delta, \tmop{degre} ( G )), D' = 0, I = 1, e = 0, E = [ ]$. On passe à l'itération suivante. \item Si $\tmop{degre} ( G ) > \delta$, on passe à l'itération suivante. \item Si $\tmop{degre} ( G ) = \delta$, on interpole: \begin{itemizearrow} \item $G := G \frac{\Delta ( \alpha )}{\tmop{lcoeff} ( G )}$ \item $D' := D' + \frac{I ( X_n )}{\prod_{\alpha_j \in E} ( \alpha - \alpha_j )} ( G - D' ( X_1, \ldots ., X_{n - 1}, \alpha ))$ \item $I := I \ast ( X_n - \alpha )$ \item $e := e + 1$ et ajouter $\alpha$ à $E$ \item Si $e$ est strictement plus grand que le minimum des degrés partiels de $P$ et $Q$ par rapport à $X_n$, on pose $\tilde{D}$ la partie primitive de $D' $(vu comme polynôme à coefficients dans $\mathbb{Z} [ X_n ]$), on teste si $P$ et $Q$ sont divisibles par $\tilde{D}$, si c'est le cas, on renvoie $D = C ( X_n ) \tilde{D}$ \end{itemizearrow} \end{itemize} \end{enumerate} On observe que dans cet algorithme, on fait le test de divisibilite de $\tilde{D}$ par $P$ et $Q$. En effet, même après avoir évalué en suffisamment de points, rien n'indique que tous ces points sont des points de bonne évaluation. En pratique cela reste extrêmement improbable. En pratique, on teste la divisibilité plus tôt, dès que $D'$ n'est pas modifié par l'ajout d'un nouveau point à la liste des $\alpha_j$. Il existe une variation de cet algorithme, appelé SPMOD (sparse modular), qui suppose que seuls les coefficients non nuls du pgcd en $n - 1$ variables sont encore non nuls en $n$ variables (ce qui a de fortes chances d'être le cas). L'étape d'interpolation est alors remplacée par la résolution d'un sous-système d'un système de Vandermonde. Cette variation est intéressante si le nombre de coefficients non nuls en $n - 1$ variables est petit devant le degré. Si elle échoue, on revient à l'interpolation dense. Notons enfin qu'on peut appliquer cette méthode lorsque les coefficients de $P$ et $Q$ sont dans $\mathbb{Z} / n \mathbb{Z}$ mais il faut alors vérifier qu'on dispose de suffisamment de points d'interpolation. Ce qui en combinant avec l'algorithme modulaire à une variable donne un algorithme doublement modulaire pour calculer le pgcd de 2 polynômes à coefficients entiers. C'est cette méthode qu'utilise par exemple MuPAD (en essayant d'abord SPMOD puis l'interpolation dense). {\tmstrong{Exemple:}} Dans cet exemple, on donne $F$ et $G$ sous forme factorisée, le but étant de faire comprendre l'algorithme. En utilisation normale, on n'exécuterait cet algorithme que si $F$ et $G$ étaient développés. $P = (( x + 1 ) y + x^2 + 1 ) ( y^2 + x y + 1 ), Q = (( x + 1 ) y + x^2 + 1 ) ( y^2 - x y - 1 )$. Prenons $x$ comme variable $X_1$ et $y$ comme variable $X_2$. Les coefficients dominants de $P$ et $Q$ sont respectivement $y$ et $- y$ donc $\Delta = y$. En $y = 0$, $P ( x, 0 ) = x^2 + 1$ n'est pas du bon degré. En $y = 1$, $P ( x, 1 ) = ( x + x^2 + 2 ) ( x + 2 )$ et $Q ( x, 1 ) = ( x + x^2 + 2 ) ( - x )$ sont du bon degré. Leur pgcd est $G = x^2 + x + 2$, $\Delta ( 1 ) = 1$, donc $D' = x^2 + x + 1$. On teste la divisibilité de $P$ par $D'$, le teste échoue. En $y = 2$, $P ( x, 2 ) = ( x^2 + 2 x + 3 ) ( 2 x + 5 )$ et $Q ( x, 2 ) = ( x^2 + 2 x + 3 ) ( - 2 x + 3 )$ donc $G = x^2 + 2 x + 3$, $\Delta ( 2 ) = 2$. On interpole: \[ D' = x^2 + x + 2 + \frac{y - 1}{2 - 1} ( 2 ( x^2 + 2 x + 3 ) - ( x^2 + x + 2 )) = y ( x^2 + 3 x + 4 ) - ( 2 x + 2 ) \] On teste la divisibilité de $P$ par $D'$, le test échoue. En $y = 3$, $P ( x, 3 ) = ( x^2 + 3 x + 4 ) ( 3 x + 10 )$ et $Q ( x, 3 ) = ( x^2 + 3 x + 4 ) ( - 3 x + 8 )$ donc $G = x^2 + 3 x + 4$, $\Delta ( 3 ) = 3$. On interpole: \begin{eqnarray*} D' &= &y ( x^2 + 3 x + 4 ) - ( 2 x + 2 ) + \\ & & \frac{( y - 2 ) ( y - 1 )}{( 3 - 2 ) ( 3 - 1 )} \left( 3 ( x^2 + 3 x + 4 ) - ( 3 ( x^2 + 3 x + 4 ) - ( 2 x + 2 )) \right) \end{eqnarray*} donc \[ D' = y ( x^2 + 3 x + 4 ) - ( 2 x + 2 ) + \frac{( y - 2 ) ( y - 1 )}{2} ( - 2 x - 2 ) = x^2 y + x y^2 + y^2 + y \] On divise $D'$ par son contenu et on trouve $x^2 + x y + y + 1$ qui est bien le pgcd de $P$ et $Q$. \subsection{EZGCD.} Il s'agit d'une méthode $p$-adique. On évalue toutes les variables sauf une, on calcule le pgcd en une variable et on remonte au pgcd variable par variable (EEZGCD) ou toutes les variables simultanément (EZGCD) par un lemme de Hensel. Il semble qu'il est plus efficace de remonter les variables séparément. Soit donc $F$ et $G$ deux polynômes primitifs dépendant des variables $X_1, \ldots, X_n$ de pgcd $D$, on fixe une des variables qu'on appelera $X_1$ dans la suite. Soient $\tmop{lcoeff} ( F )$ et $\tmop{lcoeff} ( G )$ les coefficients dominants de $F$ et $G$ par rapport à $X_1$. On évalue $F$ et $G$ en un $n - 1$ uplet $b$ tel que le degré de $F$ et $G$ par rapport à $X_1$ soit conservé après evaluation en $b$. On suppose que $D_b ( X_1 ) = \tmop{pgcd} ( F ( b ), G ( b ))$ a le même degré que $D ( b )$. On a donc l'égalité: \[ ( F \ast \tmop{lcoeff} ( F )) ( b ) = \left( D_b \frac{\tmop{lcoeff} ( F ( b ))}{\tmop{lcoeff} ( D_b )} \right) \ast \left( \frac{F ( b )}{D_b} \frac{\tmop{lcoeff} ( F ) ( b )}{\tmop{lcoeff} ( \frac{F ( b )}{D_b} )} \right) \] et de même en remplaçant $F$ par $G$. Pour pouvoir lifter cette égalité (c'est-à-dire généraliser à plusieurs variables), il faut que $D_b$ et $\frac{F ( b )}{D_b}$ soient premiers entre eux. Sinon, on peut essayer de lifter l'égalité analogue avec $G$. En général, on montre qu'il existe un entier $j$ tel que $D_b$ et $\frac{F ( b ) + j G ( b )}{D_b}$ soient premiers entre eux. En effet, sinon au moins un des facteurs irréductibles de $D_b$ va diviser $\frac{F ( b ) + j G ( b )}{D_b}$ pour deux valeurs distinctes de $j$ et va donc diviser à la fois $\frac{F ( b )}{D_b}$ et $\frac{G ( b )}{D_b}$ en contradiction avec la définition de $D_b = \tmop{pgcd} ( F ( b ), G ( b ))$. On lifte alors l'égalité obtenue en remplaçant $F$ par $( F + k G )$ ci-dessus. Dans la suite, on suppose qu'on peut prendre $j = 0$ pour alléger les notations. On va aussi supposer que $b = 0$. Sinon, on fait un changement d'origine sur les polynômes $F$ et $G$ pour que $b = 0$ convienne, on calcule le pgcd et on lui applique la translation d'origine opposée. On adopte ensuite la notation suivante: si $k$ est un entier, on dit qu'un polynôme $P$ est un $O ( k )$ si la valuation de $P$ vu comme polynôme en $X_2, \ldots ., X_n$ à coefficients dans $\mathbb{Z} [ X_1 ]$ est supérieure ou égale à $k^{}$, ou de manière équivalente si \[ P ( X_1, h X_2, \ldots ., h X_n ) = O_{h \rightarrow 0} ( h^k ) \] L'égalité à lifter se réécrit donc: \[ F \tmop{lcoeff} ( F ) = P_0 Q_0 + O ( 1 ) \] où $P_0 =$$D_b \frac{\tmop{lcoeff} ( F ( b ))}{\tmop{lcoeff} ( D_b )}$ et $Q_0 = \frac{F ( b )}{D_b} \frac{\tmop{lcoeff} ( F ) ( b )}{\tmop{lcoeff} ( \frac{F ( b )}{D_b} )}$ sont premiers entre eux et de degré 0 par rapport aux variables $X_2, \ldots ., X_n$. Cherchons $P_1 = O ( 1 )$ et $Q_1 = O ( 1 )$ de degré 1 par rapport aux variables $X_2, \ldots ., X_n$ tels que \[ F \tmop{lcoeff} ( F ) = ( P_0 + P_1 ) ( Q_0 + Q_1 ) + O ( 2 ) \] Il faut donc résoudre \[ F \tmop{lcoeff} ( F ) - P_0 Q_0 = P_0 Q_1 + Q_0 P_1 + O ( 2 ) \] On peut alors appliquer l'identité de Bézout qui permet de déterminer des polynômes $P_1$ et $Q_1$ satisfaisant l'égalité ci-dessus (avec comme reste $O ( 2 )$ nul) puisque $P_0$ et $Q_0$ sont premiers entre eux. De plus, on choisit $P_1$ et $Q_1$ tels que $\tmop{degre}_{X_1} P_1 \leqslant \tmop{degre}_{X_1} ( F ) - \tmop{degre}_{} ( Q_0 ) = \tmop{degre} ( P_0 )$ et $\tmop{degre}_{X_1} ( Q_1 ) \leqslant \tmop{degre} ( Q_0 )$ et $\tmop{lcoeff}_{X_1} ( P_0 + P_1 ) + O ( 2 ) = \tmop{lcoeff}_{X_1} ( Q_0 + Q_1 ) + O ( 2 ) = \tmop{lcoeff}_{X_1} ( F )$. On tronque ensuite $P_1$ et $Q_1$ en ne conservant que les termes de degré 1 par rapport à $X_2, \ldots ., X_n$. On trouve de la même manière par récurrence $P_k$ et $Q_k$ homogènes de degré $k$ par rapport à $X_2, \ldots ., X_k$, de degré par rapport à $X_1$ respectivement inférieur aux degrés de $Q_0$ et de $P_0$ et tels que \begin{equation} F \tmop{lcoeff} ( F ) = ( P_0 + \ldots . + P_k ) ( Q_0 + \ldots . + Q_k ) + O ( k + 1 ) \label{ezgcd} \end{equation} et $\tmop{lcoeff} ( F ) = \tmop{lcoeff}_{X_1} ( P_0 + \ldots . + P_k ) + O ( k + 1 ) = \tmop{lcoeff}_{X_1} ( Q_0 + \ldots . + Q_k ) + O ( k + 1 )$. Si on est bien en un point de bonne évaluation et si $k$ est plus grand que le degré total (par rapport aux variables $X_2, \ldots ., X_n$) du polynôme $F \tmop{lcoeff} ( F )$ on va vérifier que $P_0 + \ldots . + P_k = D \frac{\tmop{lcoeff} ( F )}{\tmop{lcoeff} ( D )}$. En effet, si on a deux suites de polynômes $P$ et $P'$ et $Q$ et $Q'$ satisfaisant (\ref{ezgcd}) avec les même termes de degré zéro $P_0$ et $Q_0$, alors en prenant la différence, on obtient: \[ ( P_0 + P_1 \ldots + P_k ) ( Q_0 + Q_1 \ldots + Q_k ) = ( P_0 + P_1' \ldots + P_k' ) ( Q_0 + Q_1' \ldots + Q_k' ) + O ( k + 1 ) \] On égale alors les termes homogènes de degré $j$, pour $j = 1$, on obtient $P_0 ( Q_1 - Q_1' ) = Q_0 ( P_1 - P_1' )$, donc $Q_0$ divise $Q_1 - Q_1'$ qui est de degré strictement inférieur au degré de $Q_0$ par rapport à $X_1$ (car on a l'inégalité large et les termes de plus haut degré sont égaux), donc $Q_1 = Q_1'$ et $P_1 = P_1'$. On montre de la même manière que $Q_j = Q_j'$ et $P_j = P_j'$. L'écriture est donc unique, c'est donc l'écriture en polynôme homogène de degré croissant de $D \frac{\tmop{lcoeff} ( F )}{\tmop{lcoeff} ( D )}$ que l'on reconstruit. Cet algorithme permet donc de reconstruire $D$, il suffit de tester à chaque étape si $P_0 + \ldots . + P_k$ divise $F \tmop{lcoeff} ( F )$. On appelle cette méthode de remontée lemme de Hensel linéaire. Il existe une variante dite lemme de Hensel quadratique qui consiste à passer de $O ( k )$ à $O ( 2 k )$. Elle nécessite toutefois un calcul supplémentaire, celui de l'identité de Bézout à $O ( 2 k )$ près pour les polynômes $P_0 + \ldots . + P_{k - 1}$ et $Q_0 + \ldots . + Q_{k - 1}$. Ce calcul se fait également par lifting. {\tmstrong{Algorithme EZGCD (Hensel linéaire)}} Arguments: 2 polynômes $F$ et $G$ à coefficients entiers et primitifs. Renvoie le pgcd de $F$ et $G$ ou false. \begin{enumerate} \item Evaluer $F$ et $G$ en $( X_2, \ldots ., X_n ) = ( 0, \ldots ., 0 )$, vérifier que les coefficients dominants de $F$ et de $G$ ne s'annulent pas. Calculer le pgcd $D_b$ de $F ( 0 )$ et de $G ( 0 )$. Prendre un autre point d'évaluation au hasard qui n'annule pas les coefficients dominants de $F$ et de $G$ et vérifier que le pgcd a le même degré que $D_b$. Sinon, renvoyer false (on peut aussi faire une translation d'origine de $F$ et de $G$ en un autre point mais cela diminue l'efficacité de l'algorithme). \item On note $\tmop{lcF}$ et $\tmop{lcG}$ les coefficients dominants de $F$ et de $G$ par rapport à $X_1$. \item Si $\tmop{degre} ( F ) \leqslant \tmop{degre} ( G )$ et $\tmop{degre} ( D_b ) = \tmop{degre} ( G )$ et $F$ divise $G$ renvoyer $F$ \item Si $\tmop{degre} ( G ) < \tmop{degre} ( F )$ et $\tmop{degre} ( D_b ) = \tmop{degre} ( F )$ et $G$ divise $F$ renvoyer $G$ \item Si $\tmop{degre} ( F ) = \tmop{degre} ( D_b )$ ou si $\tmop{degre} ( G ) = \tmop{degre} ( D_b )$ renvoyer false \item Boucle infinie sur $j$ entier initialisé à 0, incrémenté de 1 à chaque itération: si $\tmop{pgcd} ( D_b, \frac{F ( 0 ) + j G ( 0 )}{D_b} ) = C$ constant, alors arrêter la boucle \item Lifter l'égalité $( F + j G ) ( \tmop{lcF} + j \tmop{lcG} ) ( 0 ) = \left( D_b \frac{( \tmop{lcF} + j \tmop{lcG} ) ( 0 )}{\tmop{lcoeff} ( D_{b )}} \right) \ast \ldots .$ par remontée de Hensel linéaire ou quadratique. Si le résultat est false, renvoyer false. Sinon renvoyer le premier polynôme du résultat divisé par son contenu vu comme polynôme en $X_1$ à coefficients dans $\mathbb{Z} [ X_2, \ldots ., X_n ]$. \end{enumerate} {\tmstrong{Remontée de Hensel linéaire}}: Arguments: $F$ un polynôme, $\tmop{lcF}$=lcoeff$(F)$ son coefficient dominant, $P_0$ un facteur de $F ( 0 )$ ayant comme coefficient dominant $\tmop{lcF} ( 0 )$ et dont le cofacteur $Q_0$ est premier avec $P_0$. Renvoie deux polynômes $P$ et $Q$ tels que $F \tmop{lcF} = P Q$ et $P ( 0 ) = P_0$ et $\tmop{lcoeff} ( P ) = \tmop{lcoeff} ( Q ) = \tmop{lcF}$. \begin{enumerate} \item Soit $G = F \tmop{lcF}$, , $Q_0 = G ( 0 ) / P_0$, $P = P_0$, $Q = Q_0$. \item Déterminer les deux polynômes $U$ et $V$ de l'identité de Bézout (tels que $P_0 U + Q_0 V = d$ où $d$ est un entier). \item Boucle infinie avec un compteur $k$ initialisé à 1, incrémenté de 1 à chaque itération \begin{itemize} \item Si $k > \tmop{degre}_{X_2, \ldots ., X_n} ( G )$, renvoyer false. \item Si $P$ divise $G$, renvoyer $P$ et $G / P$. \item Soit $H = G - P Q = O ( k )$. Soit $u = U \frac{H}{d}$ et $v = V \frac{H}{d}$, on a $P_0 u + Q_0 v = H$ \item Remplacer $v$ par le reste de la division euclidienne de $v$ par $P_0$ et $u$ par le reste de la division euclidienne de $u$ par $Q_0$. La somme des deux quotients est égale au quotient euclidien de $H$ par $P_0 Q_0$, c'est-à-dire au coefficient dominant de $H$ divisé par le produit des coefficients dominants de $P_0$ et $Q_0$ (qui sont égaux) donc on a l'égalité: \[ P_0 u + Q_0 v = H - \frac{\tmop{lcoeff} ( H )}{\tmop{lcoeff} ( P_0 )^2} P_0 Q_0 \] \item Soit $\alpha = ( \tmop{lcoeff} ( F ) - \tmop{lcoeff} ( P )) / \tmop{lcoeff} ( P_0 )$ et $\beta = ( \tmop{lcoeff} ( F ) - \tmop{lcoeff} ( Q )) / \tmop{lcoeff} ( P_0 )$. On ajoute $\alpha P_0$ à $v$, ainsi $\tmop{lcoeff} ( P_{} + v ) = \tmop{lcoeff} ( F ) + O ( k + 1 )$ et $\beta Q_0$ à $u$, ainsi $\tmop{lcoeff} ( Q_{} + u ) = \tmop{lcoeff} ( F ) + O ( k + 1 )$ Remarque: on montre alors que $\alpha + \beta = \frac{\tmop{lcoeff} ( H )}{\tmop{lcoeff} ( P_0 Q_0 )} + O ( k + 1 )$ donc $P_0 u + Q_0 v = H + O ( k + 1 )$ en utilisant les propriétés : \[ \text{$\tmop{lcoeff} ( F ) = \tmop{lcoeff} ( P ) + O ( k ) = \tmop{lcoeff} ( Q ) + O ( k ) = \tmop{lcoeff} ( P_0 ) + O ( 1 )$} \] \item Réduire $u$ et $v$ en éliminant les termes de degré strictement supérieur à $k$ par rapport à $X_2, \ldots ., X_n$. S'il reste un coefficient non entier, renvoyer false \item Remplacer $P$ par $P + v$ et $Q$ par $Q + u$, passer à l'itération suivante. \end{itemize} \end{enumerate} {\tmstrong{Exemple}}: $F = (( x + 1 ) y + x^2 + 1 ) ( y^2 + x y + 1 ), G = (( x + 1 ) y + x^2 + 1 ) ( y^2 - x y - 1 )$ On a $F ( 0, y ) = ( y + 1 ) ( y^2 + 1 )$ et $G ( 0, y ) = ( y + 1 ) ( y^2 - 1 )$, le pgcd est donc $D_b = ( y + 1 )$. On remarque que $D_b$ est premier avec le cofacteur de $F$ mais pas avec le cofacteur de $G$. Si on évalue en un autre point, par exemple $x = 1$, on trouve un pgcd $D_1$ de même degré, donc 0 est vraissemblablement un bon point d'évaluation (ici on en est sûr puisque le pgcd de $F$ et $G$ se calcule à vue...). On a $\tmop{lcoeff} ( F ) = x + 1$, on va donc lifter $G = (( x + 1 ) y + x^2 + 1 ) ( y^2 + x y + 1 ) ( x + 1 ) = P Q$ où $P_0 = ( y + 1 )$ et $Q_0 = ( y^2 + 1 )$. On calcule les polynômes de l'identité de Bézout $U = ( 1 - y )$ et $V = 1$ avec $d = 2$, puis à l'ordre $k = 1$: \[ H = G - P_0 Q_0 = ( 2 y^3 + 2 y^2 + 3 y + 1 ) x + O ( 2 ) \] donc $u = \tmop{reste} ( U H / d, Q_0 ) = x y$ et $v = \tmop{reste} ( V H / d, P_0 ) = - x$. Donc $Q_1 = x y + \alpha Q_0$ avec $\alpha = ( x + 1 - 1 ) / \tmop{lcoeff} ( P_0 ) = x$ et $Q_0 + Q_1 = ( y^2 + 1 ) ( x + 1 ) + x y$. De même, $P_1 = - x + \beta P_0$, avec $\beta = ( x + 1 - 1 ) / \tmop{lcoeff} ( P_0 ) = x$ donc $P_0 + P_1 = ( y + 1 ) ( x + 1 ) - x$. On remarque que $P_0 + P_1$ et $Q_0 + Q_1$ sont bien à $O ( 2 )$ près les facteurs de $F \tmop{lcoeff} ( F )$: \[ P = ( x + 1 ) y + x^2 + 1 = P_0 + P_1 + O ( 2 ), \ Q = ( x + 1 ) ( y^2 + x y + 1 ) = Q_0 + Q_1 + O ( 2 ) \] Une deuxième itération est nécessaire. On calcule \[ \text{$H = G - ( P_0 + P_1 ) ( Q_0 + Q_1 ) = ( 2 y^2 + y + 1 ) x^2 + O ( 3 )$} \] puis $\tmop{reste} ( U H / d, Q_0 ) = y x^2$ et $\tmop{reste} ( V H / d, P_0 ) = x^2$. Ici les coefficients $\alpha$ et $\beta$ sont nuls car $\tmop{lcoeff} ( F )$ n'a pas de partie homogène de degré 2. On trouve alors $P = P_0 + P_1 + P_2$ et $Q = Q_0 + Q_1 + Q_2$. Pour calculer le pgcd, il suffit de calculer la partie primitive de $P$ vu comme polynôme en $y$, ici c'est encore $P$ car le contenu de $P$ est 1 (remarque: pour $Q$ le contenu est $x + 1$).\\ On trouve donc $P$ comme pgcd. \section{Quel algorithme choisir?} Il est toujours judicieux de faire une évaluation en quelques $n - 1$ uplets pour traquer les pgcd triviaux. (E)EZGCD sera efficace si (0,...,0) est un point de bonne évaluation et si le nombre de remontées nécessaires pour le lemme de Hensel est petit donc pour les pgcd de petit degré, GCDMOD est aussi efficace si le degré du pgcd est petit. Le sous-résultant est efficace pour les pgcd de grand degré car il y a alors peu de divisions euclidiennes à effectuer et les coefficients n'ont pas trop le temps de croitre. SPMOD est intéressant pour les polynômes creux de pgcd non trivial creux. GCDHEU est intéressant pour les problèmes relativement petits. Avec des machines multiprocesseurs, on a probablement intérêt à lancer en parallèle plusieurs algorithmes et à s'arrêter dès que l'un deux recontre le succès. \section{Pour en savoir plus.} Parmi les références citées dans le premier article, ce sont les livres de Knuth, H. Cohen, et Davenport-Siret-Tournier qui traitent des algorithmes de pgcd. On peut bien sûr consulter le source de son système de calcul formel lorsqu'il est disponible~: \begin{itemize} \item pour MuPAD sur un système Unix, depuis le répertoire d'installation de MuPAD (en général {\tt /usr/local/MuPAD}) après avoir désarchivé le fichier {\tt lib.tar} du répertoire {\tt share/lib} par la commande \\{\tt cd share/lib \&\& tar xvf lib.tar}\\ on trouve les algorithmes de calcul de PGCD dans le répertoire \\ {\tt share/lib/lib/POLYLIB/GCD} \item Pour l'algorithme EZGCD, je me suis inspiré de l'implémentation de Singular (logiciel libre disponible à {\tt www.singular.uni-kl.de}) \end{itemize} Sur le web on trouve quelques articles en lignes sur le sujet en cherchant les mots clefs GCDHEU, EZGCD, SPMOD sur un moteur de recherche, il y a par exemple une description un peu différente du pgcd heuristique sur:\\ {\tt www.inf.ethz.ch/personal/gonnet/CAII/HeuristicAlgorithms/node1.html}\\ et un article de comparaison de ces algorithmes par Fateman et Liao (dont la référence bibliographique est Evaluation of the heuristic polynomial GCD. in: ISSAC pages 240--247, 1995). Quelques autres références~: \begin{itemize} \item K.O.Geddes et al "Alg. for Computer Algebra", Kluwer 1992. \item pour GCDHEU Char, Geddes, Gonnet, Gcdheu: Heuristic polynomial gcd algorithm based on integer gcd computation, in: Journal of Symbolic Computation, 7:31--48, 1989. \item pour SPMOD "Probabilistic Algorithms for Sparse Polynomials", in: Symbolic \& Algebraic Comp. (Ed E.W.Ng), Springer 1979, pp216, \end{itemize} \end{document}