Factorisation exacte

Soit P un polynôme à coefficients entiers. Lorsqu'on demande à un logiciel de calcul formel de factoriser P, par défaut il ne calcule pas les racines complexes approchées, mais renvoie une factorisation exacte, sous forme de produit de facteurs à coefficients entiers. Les degrés des facteurs peuvent être plus grand que 2. Par exemple x⁴ + x + 1 ne peut pas être factorisé en produit de polynômes à coefficients entiers (bien qu'il ait 2 facteurs de degré 2 dans $\mathbb {R}$ et 4 de degré 1 dans $\mathbb {C}$).

Commencons par une méthode simple de calcul des racines rationnelles de P (les racines rationnelles correspondent à des facteurs entiers de degré 1 de la forme qX - p de P). Soit x = p/q une racine rationnelle écrite sous forme de fraction irréductible de P = a_nXⁿ + ... + a₀, on a alors

0 = P($${\frac{{p}}{{q}}}$$) = a_n$${\frac{{p^n}}{{q^n}}}$$ + a_n-1$${\frac{{p^{n-1}}}{{q^{n-1}}}}$$ + ... + a₀ = $${\frac{{a_n p^n + a_{n-1} p^{n-1}q+...+a_1 p q^{n-1}+ a_0 q^n}}{{q^n}}}$$

Donc :

p(a_np^n-1 + a_n-1p^n-1q + ... + a₁q^n-1) = - a₀qⁿ

et p divise donc a₀qⁿ. Comme p/q est irréductible, cela entraine que p divise a₀. De même q divise a_n. Il suffit donc de tester quelles sont les racines de P parmi toutes les fractions irréductibles de la forme un diviseur de a₀ sur un diviseur de a_n (attention à ne pas oublier les diviseurs négatifs!).

Exemple: racines rationnelles de 2x² + 3x + 1 = 0. On a p divise 1 donc vaut 1 ou -1, q divise 2 donc vaut 1 ou 2. On teste donc 1, -1, 1/2, -1/2. On obtient ici la factorisation complète du polynome (les racines sont -1 et -1/2)

2x² + 3x + 1 = 2(x + 1)(x + 1/2)

Remarques :

• Pour un polynome aléatoire, on ne trouvera aucune racine rationnelle.
• Cette méthode n'est pas très efficace, car factoriser un entier peut être long, le nombre de tests peut être très grand (si a_n et a₀ ont beaucoup de facteurs), les logiciels de calcul formel utilisent des méthodes appelées p-adiques pour trouver les racines rationnelles d'un polynome (on calcule d'abord les racines de P modulo p puis modulo p^k pour k assez grand). On pourrait aussi penser à calculer les racines complexes approchées et voir si en multipliant par a_n on est proche d'un entier, on testerait alors le rationnel correspondant.

Pour déterminer les facteurs à coefficients entiers de plus grand degré, il n'existe pas de méthode aussi simple. On peut calculer des valeurs approchées des racines complexes et essayer de créer des paquets de racines complexes, puis tester si a_n$\prod_{{r \in \mbox{paquet}}}^{}$(X - r) est à coefficients entier (aux erreurs d'arrondi près). Par exemple si on calcule les racines complexes approchées de x⁶ +2x³ - x² + 1, on pourra composer un facteur de degré 3 à coefficients entiers en rassemblant les racines de x³ + x + 1. Les logiciels de calcul formel utilisent des algorithmes modulaires et p-adiques (consistant à factoriser le polynome modulo p).