Factorisation des polynômes

En mathématiques, la factorisation d'un polynôme consiste à écrire celui-ci comme produit de polynômes. Les factorisations intéressantes sont celles permettant d'écrire le polynôme initial en produit de plusieurs polynômes non inversibles. Un polynôme non inversible pour lequel aucune factorisation de ce type n'existe s'appelle un polynôme irréductible.

La décomposition d'un polynôme en produits de polynômes irréductibles existe, et a une propriété d'unicité (à un facteur inversible près), pour tout polynôme à coefficients réels ou complexes. Ceci est encore vrai lorsque les coefficients sont dans un anneau factoriel, que le polynôme soit à une ou plusieurs indéterminées. Cette propriété est, pour l'ensemble des polynômes, analogue au théorème fondamental de l'arithmétique pour l'ensemble des entiers.

La recherche d'une factorisation est un problème algorithmique de difficulté variable suivant, en premier lieu, l'anneau de coefficients considéré, et en second lieu, la taille de ces coefficients et le degré du polynôme.

La factorisation d'un polynôme est utile pour décomposer une fraction rationnelle en somme d'éléments simples.

Polynômes à coefficients réels ou complexes

Polynômes à coefficients réels

Méthodes élémentaires

Les identités remarquables et la propriété de distributivité de la multiplication sur l'addition fournissent des méthodes élémentaires de factorisation de polynômes

Exemples

• $3x^{2}+9=3(x^{2}+3)$
• $4x^{2}-8x=4x(x-2)$
• $x^{2}+2ax+a^{2}=(x+a)^{2}$
• $x^{2}-b^{2}=(x-b)(x+b)$
• $\forall n\geq 1,\,x^{n}-r^{n}=(x-r)(x^{n-1}+rx^{n-2}+\cdots r^{k}x^{n-1-k}+\cdots +r^{n-1})$

La première des factorisations ne décompose pas le polynôme en produit de polynômes de degré moindre. Cependant, elle offre l'avantage de présenter un polynôme dont le coefficient du terme de plus haut degré est 1. De tels polynômes sont dits unitaires et sont utilisés dans les décompositions pour garantir l'unicité de celles-ci.

La dernière factorisation offre un moyen de prouver que tout polynôme P possédant r comme racine peut s'écrire

$P(x)=(x-r)Q(x)$

où Q est de degré inférieur au degré de P.

Démonstration

L'identité remarquable précédente affirme que

$\forall k\geq 1,x^{k}-r^{k}=(x-r)p_{k}(x)$

où $p_{k}$ est un polynôme de degré k-1

Soit alors P le polynôme

$P(x)=\sum _{k=0}^{n}a_{k}x^{k}$

Puisque r est une racine de P, on a P(r)=0, donc

$P(x)=P(x)-P(r)=\sum _{k=1}^{n}a_{k}(x^{k}-r^{k})=(x-r)\left(\sum _{k=1}^{n}a_{k}p_{k}(x)\right)=(x-r)Q(x)$

Cependant, en pratique, quand une racine r est connue, la factorisation précédente se calcule plutôt en utilisant une division de polynôme ou la méthode de Horner.

Polynômes irréductibles

Sur tout corps, les polynômes irréductibles sont les polynômes qui ne peuvent pas se décomposer en produit de deux polynômes non constants. Les polynômes de degré 1 sont donc toujours irréductibles.

Un polynôme de degré 2 qui pourrait s'écrire comme produit de polynômes de degré 1 possèderait des racines. Par contraposée, un polynôme de degré 2 ne possédant pas de racine est irréductible. Sur ℝ, c'est le cas de tous les polynômes de degré 2 dont le discriminant est négatif (voir l'article Équation du second degré).

On démontre que les seuls polynômes à coefficients réels irréductibles sont de ce type (polynômes de degré 1 ou polynôme de degré 2 dont le discriminant est négatif). Ce résultat est une conséquence du théorème de d'Alembert-Gauss, qui porte sur les polynômes à coefficients complexes.

Ainsi le polynôme réel

$P(x)=x^{4}+4,$

qui ne semble pas factorisable de manière simple (il ne possède pas de racine), n'est pas irréductible (en fait, il est factorisable grâce à l'identité de Sophie Germain).

$P(x)=x^{4}+4x^{2}+4-4x^{2}=(x^{2}+2)^{2}-(2x)^{2}=(x^{2}-2x+2)(x^{2}+2x+2).$

Ce même théorème de d'Alembert-Gauss permet aussi de prouver que la décomposition (unique à l'ordre près) de tout polynôme à coefficients réels est de la forme

$a_{n}(x-r_{1})^{\alpha _{1}}\cdots (x-r_{k})^{\alpha _{k}}\prod _{i=1}^{l}p_{i}(x)^{\beta _{i}}$

où les p_i sont des polynômes irréductibles unitaires de degré 2.

Racines et factorisation

Le lien existant entre les racines d'un polynôme et sa factorisation justifie les études portant sur ses racines. Les recherches s'orientent dans deux directions : recherche de racines exactes éventuellement par incursion dans les complexes et recherche de racines approchées.

La première voie a conduit à l'étude des coefficients des polynômes, qui d'après le théorème de Viète, s'expriment comme polynômes symétriques des racines. Cette voie de recherche, fructueuse sur les polynômes de degré 3 et 4, et sur certains polynômes de degré supérieur a laissé croire qu'il serait possible de déterminer toutes les racines d'un polynôme en utilisant seulement des opérations de somme, produit, quotient et extraction de racine nième, quitte à passer par les complexes. Si les racines d'un polynôme s'écrivent effectivement ainsi, on dit qu'il est résoluble par radicaux. Dans le courant du XIX^e siècle, Niels Henrik Abel démontre que les équations polynomiales de degré supérieur ou égal à 5 ne sont pas toutes résolubles par radicaux (théorème d'Abel). Une classification des équations résolubles par radicaux est donnée par la théorie de Galois.

La seconde voie est la recherche de racines approchées de polynômes. Ce sont les algorithmes de recherche d'un zéro d'une fonction dont un des classiques est la méthode de Newton. Ces méthodes nécessitent de déterminer combien de racines se trouvent dans un intervalle donné. Descartes par sa règle des signes permet de déterminer le nombre de changements de signe d'un polynôme en observant seulement le signe de ses coefficients et par la même le nombre de racines. Le théorème de Sturm permet de déterminer le nombre de racines dans un intervalle donné d'un polynôme ne comportant que des racines simples. Il permet aussi de séparer les racines dans des intervalles distincts.

Polynômes à coefficients complexes

Comme il est indiqué dans la section précédente, la recherche des polynômes irréductibles à coefficients réels et la factorisation des polynômes nécessite une incursion dans les complexes où les factorisations ont une présentation simple.

Dans l'ensemble des complexes les seuls polynômes irréductibles sont les polynômes de degré 1 et tout polynôme P complexe de degré n se décompose de manière unique sous la forme suivante :

$P(x)=a_{n}\prod _{i=1}^{k}(x-r_{i})^{\alpha _{i}}$

avec $\sum _{i=1}^{k}\alpha _{i}=n$

La racine $r_{i}$ est dite d'ordre $\alpha _{i}$.

Mais les mêmes difficultés persistent sur la mise en place effective d'une factorisation.

Démonstration

Soit $P\in \mathbb {R} [X]$ un polynôme irréductible de degré supérieur ou égal à 2.

$P$ n'admet pas de racines dans $\mathbb {R}$, mais comme $P\in \mathbb {C} [X]$, $P$ admet une racine $\alpha$ dans $\mathbb {C}$. De plus $P$ étant irréductible dans $\mathbb {R} [X]$, $\alpha \not \in \mathbb {R}$.

Il existe donc $Q\in \mathbb {C} [X]$ tel que $P=(X-\alpha )Q$.

Dans $\mathbb {C} [X]$, le conjugé de $P$ est ${\overline {P}}=\left(X-{\overline {\alpha }}\right){\overline {Q}}$. Mais comme $P\in \mathbb {R} [X]$, $P={\overline {P}}=\left(X-{\overline {\alpha }}\right){\overline {Q}}$. Donc ${\overline {\alpha }}$ est une racine de $P$.

Comme $\alpha \neq {\overline {\alpha }}$, $P$ est divisible par $\left(X-\alpha \right)\left(X-{\overline {\alpha }}\right)=X^{2}-(\alpha +{\overline {\alpha }})X+\alpha {\overline {\alpha }}\in \mathbb {R} [X]$.

Comme $P$ est irréductible $P=\lambda \left(X^{2}-(\alpha +{\overline {\alpha }})X+\alpha {\overline {\alpha }}\right)$ avec $\lambda \in \mathbb {R}$.

Ainsi $P$ est de degré 2, il n'y a donc pas de polynôme irréductible de degré supérieur ou égal à 3 dans $\mathbb {R} [X]$.

Exemples

Considérons le polynôme $X^{4}-1\,$ à coefficients dans $\ \mathbb {R}$ ou $\mathbb {C}$.

• L'identité remarquable $a^{2}-b^{2}=(a+b)(a-b)\,$ donne :

$X^{4}-1=(X^{2}+1)(X^{2}-1)\,$

puis :

$\ X^{4}-1=(X^{2}+1)(X-1)(X+1)$.

Ceci est la factorisation en produit de facteurs irréductibles à coefficients dans $\ \mathbb {R}$.

Ainsi,on a le signe de $X^{4}-1\,$ en fonction de X (réel, bien entendu) :

X < -1 ou X > 1 ⇒ P(X) > 0

-1 < X < 1 ⇒ P(X) < 0

• La factorisation en produit de facteurs irréductibles à coefficients dans $\mathbb {C}$ est :

$\ X^{4}-1=(X+i)(X-i)(X-1)(X+1)$.

Plus généralement, on sait factoriser dans $\mathbb {C}$ puis dans $\mathbb {R}$, tout polynôme P de la forme $X^{n}-a$ où a > 0. Si on note

$b={\sqrt[{n}]{a}}$

les racines de P sont :

$r_{k}=be^{i2k\pi /n}$

et P a pour décomposition dans $\mathbb {C}$:

$P(X)=\prod _{k=0}^{n-1}(X-be^{i2k\pi /n})$

La décomposition dans $\mathbb {R}$ consiste à regrouper les racines conjuguées. La décomposition est différente selon que n est pair ou impair.

Polynômes à coefficients dans un anneau

Lorsque les coefficients ne sont pas réels ou complexes, les polynômes irréductibles peuvent être de degré supérieur à 2 et l'existence d'une factorisation en produit de polynômes irréductible n'est pas garantie.

Polynômes irréductibles

On appelle polynôme irréductible tout polynôme P non inversible dont les seuls diviseurs sont les polynômes inversibles et les polynômes associés à P. En d'autres termes

P est irréductible ssi $\forall (Q,R)\in A[X]^{2}\quad P=QR\Rightarrow$ exactement l'un des deux facteurs Q ou R est inversible.

Même sur un anneau intègre,

• un polynôme de degré 0 ou 1 n'est pas nécessairement irréductible. Par exemple dans $\mathbb {Z} [X]$, $6=2\times 3$ et $6X=2\times (3X)$.
• un polynôme irréductible de degré (supérieur ou) égal à 2 n'a pas de racine, mais un polynôme de degré 2 sans racine n'est pas nécessairement irréductible. Par exemple dans $\mathbb {Z} [X]$, $2X^{2}+2=2\times (X^{2}+1)$.

Des polynômes réductibles sur $\mathbb {R}$ peuvent se révéler irréductibles sur $\mathbb {Q}$ : $X^{2}-2$ est réductible dans $\mathbb {R} [X]$ mais irréductible dans $\mathbb {Q} [X]$ .

Le lemme de Gauss permet d'affirmer que tout polynôme non constant et irréductible dans $\mathbb {Z} [X]$ l'est aussi dans $\mathbb {Q} [X]$.

Le critère d'Eisenstein fournit une condition suffisante pour qu'un polynôme primitif P de $\mathbb {Z} [X]$ soit irréductible : il suffit de trouver un nombre premier $p$ divisant tous les coefficients de P sauf le coefficient du terme de plus haut degré et tel que $p^{2}$ ne divise pas le terme constant. Ainsi

$X^{4}-9X^{3}+3X^{2}-6X+15$ est irréductible dans $\mathbb {Z} [X]$ car 3 divise tous les coefficients sauf celui du terme de degré 4 et 9 ne divise pas 15.

Factorisation

Si A est un anneau intègre dont tous les éléments possèdent une décomposition en facteurs irréductibles unique à un inversible près, c'est-à-dire si A est un anneau factoriel alors tout polynôme de A[X] possède aussi une décomposition unique en produit de polynômes irréductibles à un inversible près.

Un corps étant un exemple d'anneau factoriel, tout polynôme non constant de $\mathbb {K} [X]$ possède une décomposition unique sous forme de produit de polynômes unitaires irréductibles multiplié par une constante.

Polynômes en plusieurs indéterminées

Si A est un anneau factoriel, A[X] est factoriel, puis A[X][Y] = A[X,Y] est aussi factoriel et il en est de même de $A[X_{1},X_{2},\cdots ,X_{n}]$. Un polynôme à n indéterminées sur un anneau factoriel est donc toujours décomposable de manière unique (à un inversible près) en produits de polynômes irréductibles.

Algorithmes de décomposition

Suivant la nature de l'anneau des coefficients considéré, les algorithmes de factorisation des polynômes en produits d'irréductibles sont de difficulté variable.

Polynômes à coefficients réels ou complexes

Dans le cas de coefficients réels ou complexes, l'obtention d'une factorisation exacte avec des coefficients en écriture décimale est en général impossible, puisque l'écriture d'une racine requiert une infinité de décimales. Cependant de nombreux algorithmes, dont le plus célèbre est la méthode de Newton, permettent d'obtenir des approximations aussi bonnes que souhaitées. Un tel algorithme itératif, sous de bonnes conditions de départ, peut doubler (voire mieux) le nombre de décimales obtenues à chaque itération. Des conditions de départ acceptables peuvent être obtenues en utilisant au préalable des algorithmes de séparation des racines. Le cas des racines multiples, ou extrêmement rapprochées, nécessite des considérations particulières.

Polynômes à coefficients dans un corps fini

Dans le cas des polynômes à coefficients dans les corps finis, pour un polynôme fixé, il n'existe qu'un nombre fini de diviseurs potentiels, les polynômes de degré inférieur. Un algorithme naïf consiste donc à factoriser un polynôme en testant sa divisibilité par les polynômes de degré inférieur, de manière analogue à l'algorithme naïf de division des entiers. Toutefois, des algorithmes bien plus efficaces existent. Ils ont été découverts entre la fin des années 1960 et le début des années 1980, et sont de complexité polynomiale, déterministe ou probabiliste, par exemple l'algorithme de Berlekamp, ou celui de Cantor-Zassenhaus. De la factorisation des polynômes à coefficients dans les corps finis se déduisent des algorithmes de factorisation dans d'autres domaines. D'abord pour les polynômes dont les coefficients sont des nombres p-adiques, avec la restriction, comme dans le cas des coefficients réels et complexes, qu'on ne peut obtenir en temps fini qu'un nombre fini de termes d'un développement p-adique (les facteurs irréductibles peuvent être de tout degré, et pas seulement de degré 1 ou 2 comme dans les cas réel et complexe).

Polynômes à coefficients entiers ou rationnels

En multipliant un polynôme à coefficients rationnels par le dénominateur commun à tous ses coefficients, on se ramène à un polynôme à coefficients entiers. Les factorisations dans $\mathbb {Q} [X]$ ou dans $\mathbb {Z} [X]$ sont donc équivalentes.

Les algorithmes de factorisation de polynômes à coefficients entiers effectuent d'abord une factorisation dans un corps fini $\mathbb {F} _{p}$ grâce à l'algorithme de Berlekamp et remontent celle-ci dans un corps fini plus grand $\mathbb {Z} /_{p^{k}\mathbb {Z} }$ à l'aide du lemme de Hensel. La factorisation dans $\mathbb {Z} [X]$ s'obtient alors en regroupant les facteurs. La méthode la plus simple consiste alors à tester toutes les possibilités mais celle-ci est de complexité exponentielle. Une autre méthode est de ramener ce problème à un problème de type sac à dos puis de le résoudre à l'aide de l'algorithme LLL.

Concrètement, l'idée de l'algorithme est la suivante : on se donne un polynôme $P$, que l'on peut considérer sans perte de généralité unitaire sans facteurs carrés, et on le factorise en $P=GH$ dans $\mathbb {F} _{p}$ avec $p$ premier, choisi tel que $P$ reste sans facteurs carrés. Cette factorisation est alors remontée en $P={\hat {G}}{\hat {H}}$ dans $\mathbb {Z} /_{p^{k}\mathbb {Z} }$ avec $k$ choisi tel que $||P||^{2n-1}\cdot n^{\dfrac {n}{2}}\cdot {\begin{pmatrix}n-1\\\left\lfloor {\dfrac {n-1}{2}}\right\rfloor \end{pmatrix}}^{n}\cdot 2^{\dfrac {n(n-1)}{2}}<p^{kl}$

où $n$ est le degré de $P$ et $l$ celui de $G$. On considère alors une base du réseau $\{p^{k}X^{i}\mid 0\leq i<l\}\cup \{{\hat {G}}X^{i}\mid 0\leq i<n-l\}$ que l'on réduit avec LLL. La condition sur $k$ assure alors que si le premier vecteur de la base réduite est premier avec $P$, alors $P$ est irréductible et sinon, leur PGCD est un facteur non constant de $P$. Il ne reste alors plus qu'à itérer l'algorithme pour factoriser entièrement $P$.

Cette méthode est de complexité polynomiale mais est en pratique plus longue que celle qui est exponentielle. Cependant, depuis le début des années 2000, les algorithmes de van Hoeij ont amélioré cette méthode et ont permis de factoriser des polynômes qui étaient jusque-là inaccessibles.

Voir aussi

Articles connexes

• Algorithme LLL
• Arithmétique des polynômes
• Critère d'irréductibilité de Cohn
• Primalité dans un anneau
• Conjecture de Casas-Alvero

Bibliographie

(en) Victor V. Prasolov, Polynomials, Springer, 2010 (1^re éd. 2004) (lire en ligne), p. 49-50, 71-73 et 279-288