Factorisation des polynômes

mathématiques et en calcul formel , la factorisation de polynômes consiste à exprimer un polynôme à coefficients appartenant à un corps donné ou à l' ensemble des entiers comme le produit de facteurs irréductibles à coefficients appartenant au même corps. La factorisation de polynômes est l'un des composants fondamentaux des systèmes de calcul formel .

Le premier algorithme de factorisation polynomiale a été publié par Theodor von Schubert en 1793. Leopold Kronecker a redécouvert l'algorithme de Schubert en 1882 et l'a étendu aux polynômes multivariés et à leurs coefficients dans une extension algébrique . Cependant, la plupart des connaissances sur ce sujet ne sont pas antérieures à 1965 environ et aux premiers systèmes de calcul formel par ordinateur :

Lorsque les algorithmes à pas finis, connus depuis longtemps, ont été implémentés pour la première fois sur ordinateur, ils se sont révélés extrêmement inefficaces. Le fait que presque tout polynôme univarié ou multivarié de degré inférieur ou égal à 100 et à coefficients de taille modérée (jusqu'à 100 bits) puisse être factorisé par les algorithmes modernes en quelques minutes de temps de calcul témoigne du succès rencontré par ce problème au cours des quinze dernières années. (Erich Kaltofen, 1982)

Les algorithmes et les ordinateurs modernes peuvent rapidement factoriser des polynômes univariés de degré supérieur à 1000 ayant des coefficients à plusieurs milliers de chiffres. À cette fin, même pour la factorisation sur les nombres rationnels et les corps de nombres , une étape fondamentale est la factorisation d'un polynôme sur un corps fini .

Les anneaux de polynômes sur les entiers ou sur un corps sont des anneaux factoriels uniques . Cela signifie que tout élément de ces anneaux est le produit d'une constante et d'un produit de polynômes irréductibles (c'est-à-dire des polynômes qui ne sont pas le produit de deux polynômes non constants). De plus, cette décomposition est unique à la multiplication des facteurs par des constantes inversibles près.

La factorisation dépend du corps de base. Par exemple, le théorème fondamental de l'algèbre , qui stipule que tout polynôme à coefficients complexes possède des racines complexes, implique qu'un polynôme à coefficients entiers peut être factorisé (à l'aide d'algorithmes de recherche de racines ) en facteurs linéaires sur le corps complexe C. De même, sur le corps des réels , les facteurs irréductibles sont de degré au plus deux, tandis que sur le corps des rationnels Q , il existe des polynômes de tout degré qui sont irréductibles.

La question de la factorisation polynomiale n'a de sens que pour les coefficients d'un corps calculable dont chaque élément peut être représenté par ordinateur et pour lequel il existe des algorithmes pour les opérations arithmétiques. Cependant, cette condition n'est pas suffisante : Fröhlich et Shepherdson donnent des exemples de tels corps pour lesquels aucun algorithme de factorisation ne peut exister.

Les corps de coefficients pour lesquels on connaît des algorithmes de factorisation comprennent les corps premiers (c’est-à-dire le corps des nombres rationnels et le corps des entiers modulo un nombre premier ) et leurs extensions de type fini . Les coefficients entiers sont également traitables. La méthode classique de Kronecker ne présente d’intérêt que d’un point de vue historique ; les algorithmes modernes procèdent par une succession d’étapes :

Factorisation sans carré
Factorisation sur les corps finis

et réductions :

Du cas multivarié au cas univarié .
Des coefficients dans une extension purement transcendantale au cas multivarié sur le corps de base (voir ci-dessous ).
Des coefficients dans une extension algébrique aux coefficients dans le corps de base (voir ci-dessous ).
Des coefficients rationnels aux coefficients entiers (voir ci-dessous ).
Des coefficients entiers aux coefficients dans un corps premier à p éléments, pour un p bien choisi (voir ci-dessous ).

Factorisation primitive partie-contenu

à son signe près, le plus grand commun diviseur de ses coefficients. La partie primitive de p est primpart( p ) = p / cont( p ), qui est un polynôme primitif à coefficients entiers. Ceci définit une factorisation de p en le produit d'un entier et d'un polynôme primitif. Cette factorisation est unique à un signe près du contenu. Par convention, on choisit le signe du contenu de sorte que le coefficient dominant de la partie primitive soit positif.

Par exemple,

est une factorisation en contenu et partie primitive.

Tout polynôme q à coefficients rationnels peut être écrit

où p ∈ Z [ X ] et c ∈ Z : il suffit de prendre pour c un multiple de tous les dénominateurs des coefficients de q (par exemple leur produit) et p = cq . Le contenu de q est défini comme :

La partie primitive de q est celle de p . Quant aux polynômes à coefficients entiers, cela définit une factorisation en un nombre rationnel et un polynôme primitif à coefficients entiers. Cette factorisation est unique à un signe près.

Par exemple,

est une factorisation en contenu et partie primitive.

Gauss a démontré que le produit de deux polynômes primitifs est lui-même primitif ( lemme de Gauss ). Il en découle qu'un polynôme primitif est irréductible sur les rationnels si et seulement s'il est irréductible sur les entiers. Cela implique également que la factorisation sur les rationnels d'un polynôme à coefficients rationnels est identique à la factorisation sur les entiers de sa partie primitive. De même, la factorisation sur les entiers d'un polynôme à coefficients entiers est égale au produit de la factorisation de sa partie primitive par la factorisation de son contenu.

En d'autres termes, le calcul du PGCD entier réduit la factorisation d'un polynôme sur les rationnels à la factorisation d'un polynôme primitif à coefficients entiers, et la factorisation sur les entiers à la factorisation d'un entier et d'un polynôme primitif.

Tout ce qui précède reste vrai si l'on remplace Z par un anneau de polynômes sur un corps F et Q par un corps de fonctions rationnelles sur F à partir des mêmes variables, à la seule différence que « à un signe près » doit être remplacé par « à la multiplication près par une constante inversible dans F ». Ceci ramène la factorisation sur une extension purement transcendante de F à la factorisation de polynômes multivariés sur F.

Factorisation sans carré

dérivée du polynôme (par rapport à n'importe laquelle des variables, s'il y en a plusieurs).

Pour les polynômes univariés, la présence de plusieurs facteurs équivaut à celle de plusieurs racines (sur un corps d'extension approprié). Pour les polynômes univariés sur les rationnels (ou plus généralement sur un corps de caractéristique nulle), l'algorithme de Yun exploite cette propriété pour factoriser efficacement le polynôme en facteurs non carrés, c'est-à-dire des facteurs qui ne sont pas des multiples d'un carré, en effectuant une suite de calculs de PGCD commençant par pgcd( f ( x ), f '( x )). Pour factoriser le polynôme initial, il suffit de factoriser chaque facteur non carré. La factorisation sans facteur carré est donc la première étape de la plupart des algorithmes de factorisation de polynômes.

L'algorithme de Yun étend cela au cas multivarié en considérant un polynôme multivarié comme un polynôme univarié sur un anneau de polynômes.

Dans le cas d'un polynôme sur un corps fini, l'algorithme de Yun n'est applicable que si le degré est inférieur à la caractéristique, car, sinon, la dérivée d'un polynôme non nul peut être nulle (sur le corps à p éléments, la dérivée d'un polynôme en x<sup> ^p</sup> est toujours nulle). Néanmoins, une succession de calculs de PGCD, à partir du polynôme et de sa dérivée, permet de calculer la décomposition sans facteur carré ; voir Factorisation de polynômes sur des corps finis#Factorisation sans facteur carré .

méthodes classiques

Cette section décrit les méthodes classiques qui peuvent s'avérer pratiques pour le calcul manuel. Ces méthodes ne sont pas utilisées pour les calculs sur machine car elles font appel à la factorisation d'entiers , actuellement plus lente que la factorisation de polynômes.

Les deux méthodes qui suivent partent d'un polynôme univarié à coefficients entiers pour trouver des facteurs qui sont également des polynômes à coefficients entiers.

Obtention des facteurs linéaires

Tous les facteurs linéaires à coefficients rationnels peuvent être trouvés à l'aide du test de la racine rationnelle . Si le polynôme à factoriser est $, alors tous les facteurs linéaires possibles sont de la forme, où est un facteur entier de et est un facteur entier de Toutes les combinaisons possibles de facteurs entiers peuvent être testées, et chaque combinaison valide peut être factorisée par la division euclidienne des polynômes . Si le polynôme initial est le produit de facteurs dont au moins deux sont de degré 2 ou supérieur, cette technique ne fournit qu'une factorisation partielle ; sinon, la factorisation est complète. En particulier, s'il existe exactement un facteur non linéaire, il s'agira du polynôme restant après la factorisation de tous les facteurs linéaires. Dans le cas d'un polynôme cubique, si celui-ci est factorisable, le test de la racine rationnelle donne une factorisation complète, soit en un facteur linéaire et un facteur quadratique irréductible, soit en trois facteurs linéaires.$

La méthode de Kronecker

La méthode de Kronecker vise à factoriser les polynômes univariés à coefficients entiers en polynômes à coefficients entiers.

La méthode repose sur le fait que l'évaluation de polynômes entiers à des valeurs entières doit produire des entiers. Autrement dit, si $est un polynôme à coefficients entiers, alors est un entier dès que est un facteur de la valeur de doit être l'un des facteurs de$

Si l'on recherche tous les facteurs d'un degré donné $valeurs, pour tuple Chaque possède un nombre fini de diviseurs et, chacun -tuple où le l'entrée est un diviseur de, c'est-à-dire un tuple de la forme, produit un polynôme unique de degré au plus, qui peut être calculé par interpolation polynomiale . On peut vérifier si chacun de ces polynômes est un facteur par division polynomiale . Comme il y en avait un nombre fini et chaque Si un tuple possède un nombre fini de diviseurs, il existe un nombre fini de tels tuples. Ainsi, une recherche exhaustive permet de trouver tous les facteurs de degré au plus .$

Si ce polynôme se factorise sur Z , alors au moins un de ses facteurs $doit être de degré deux ou moins, donc est déterminé de manière unique par trois valeurs . Ainsi, nous calculons trois valeurs., et Si l'une de ces valeurs est 0, nous avons un facteur linéaire. Si les valeurs sont non nulles, nous pouvons lister les factorisations possibles pour chacune. Or, 2 ne peut se factoriser que comme suit :$

1×2, 2×1, (−1)×(−2), ou (−2)×(−1).

Par conséquent, s'il existe un facteur polynomial entier du second degré, il doit prendre l'une des valeurs

p (0) = 1, 2, −1 ou −2

et de même pour p (−1). Il existe huit factorisations de 6 (quatre pour 1×6 et quatre pour 2×3), ce qui donne un total de 4×4×8 = 128 triplets possibles ( p (0), p (1), p (−1)), dont la moitié peut être éliminée comme étant l'opposé de l'autre moitié. Il faut donc vérifier 64 polynômes entiers explicites. $comme facteurs possibles de Des tests exhaustifs révèlent que$

construit à partir des facteurs ( g (0), g (1), g (−1)) = (1,3,1) $.$

La division de f ( x ) par p ( x ) donne l'autre facteur $, de sorte que On peut maintenant tester récursivement pour trouver les facteurs de p (x) et q (x), en utilisant dans ce cas le test de la racine rationnelle. Il s'avère qu'ils sont tous deux irréductibles, donc la factorisation irréductible de f (x) est :$

méthodes modernes

Factorisation sur les corps finis

est un polynôme univarié sur les entiers, supposé sans contenu et sans carré ; on commence par calculer une borne

Factorisation sur les extensions algébriques (méthode de Trager)

On peut factoriser un polynôme $, où le champ est une extension finie de Tout d'abord, en utilisant la factorisation sans facteur carré, nous pouvons supposer que le polynôme est sans facteur carré. Ensuite, nous définissons l' anneau quotient. de diplôme; ceci n'est pas un champ sauf si est irréductible, mais c'est un anneau réduit puisque est sans carré. En effet, si$

est la factorisation souhaitée de p ( x ), l'anneau se décompose de manière unique en corps comme :

Nous allons trouver cette décomposition sans connaître la factorisation. Tout d'abord, nous écrivons L explicitement comme une algèbre sur $: nous choisissons un élément aléatoire, qui génère sur avec une forte probabilité d'après le théorème des éléments primitifs . Dans ce cas, nous pouvons calculer le polynôme minimal. de sur, en trouvant un relation linéaire entre 1, α, ..., α<sub> n</sub> . En utilisant un algorithme de factorisation pour les polynômes rationnels, nous factorisons en termes irréductibles. :$

Nous avons donc :

où $correspond à . Ceci doit être isomorphe à la décomposition précédente de .$

Les générateurs de L sont x ainsi que les générateurs de $sur; en les écrivant sous forme de polynômes en, nous pouvons déterminer les plongements de et dans chaque composant En trouvant le polynôme minimal de dans, nous calculons, et donc facteur sur$

Polynômes au carré

Factoriser un polynôme au carré en ses racines carrées

En général, la plupart des polynômes n'ont pas de racine carrée. Cependant, certaines applications, comme la fonction utilisée par les ingénieurs électriciens pour obtenir les paramètres Y à partir de l'impédance du point d'entrée d'un réseau à deux ports , font appel à des polynômes au carré qui doivent être factorisés en deux polynômes à racine carrée identiques. L'algorithme ci-dessous permet de factoriser un polynôme au carré. $, en deux racines polynomiales identiques,, en utilisant un exemple tiré de Mathematics Stack Exchange .$

Mesures:

Étape 1 : Calculer la racine carrée du terme dominant, $et placez-le,, dans le terme dominant de la solution polynomiale R ligne en haut, et placez le terme de la ligne 1 juste en dessous du polynôme à factoriser, comme indiqué.$

Étape 2 : Soustraire le nouveau placé $du polynôme à factoriser, et abaissez les deux termes suivants dans la ligne 2.$

Étape 3 : Doublez l'état actuel du polynôme de solution R, puis ajoutez un nouveau terme, Q, tel que R(2Q+R) nie le terme principal de la ligne 2, et placez le négatif de R(2Q+R) dans l'espace inférieur de la ligne 2.

Étape 4 : Soustrayez les deux nombres de la ligne 2, placez les résultats dans la ligne 3 et reportez les deux termes suivants de la ligne 1 dans la ligne 3.

Étape 5 : Répétez l’opération pour toutes les lignes et colonnes restantes jusqu’à ce que ce soit terminé.

Une fois le calcul terminé, le polynôme R de la solution apparaîtra dans la colonne R du tableau de gauche et dans la ligne R du tableau de droite.

solution générale de racine carrée polynomiale

L'algorithme de calcul de la racine carrée d'un polynôme présenté ci-dessus peut être résumé et généralisé en une syntaxe mathématique standard permettant d'extraire les racines carrées de polynômes au carré de toute taille. Il est facilement traduisible en langage informatique pour des calculs rapides. Si le terme de plus haut degré du polynôme au carré est différent de 1, il faut d'abord le diviser par la valeur de ce terme, puis multiplier les facteurs obtenus par la racine carrée de ce même terme. En résumé, voici l'algorithme :

$.$

Notez qu'une fois $a été calculé pour, le polynôme R a été complété et ce qui suit et Les calculs peuvent être négligés dans la mesure où les résultats ne sont plus utilisés après ce point, mais s'ils sont exécutés, les résultats peuvent être utilisés comme vérification de validité pour s'assurer que le polynôme S est un polynôme au carré et que l'algorithme a été exécuté correctement en s'assurant que les valeurs finales des vecteurs T et D sont identiques, comme indiqué dans le tableau.$

Factorisation numérique

à virgule flottante .

Pour les polynômes univariés à coefficients complexes, la factorisation peut facilement être réduite au calcul numérique des racines et des multiplicités polynomiales .

Dans le cas multivarié, une perturbation infinitésimale aléatoire des coefficients produit avec une probabilité de un un polynôme irréductible , même à partir d'un polynôme à plusieurs facteurs. Il est donc nécessaire de préciser la signification même de la factorisation numérique .

Laisser $soit un polynôme à coefficients complexes avec une factorisation irréductible$

où $et les facteurs sont des polynômes irréductibles à coefficients complexes. Supposons que est approchée par un polynôme dont les coefficients sont proches de ceux de La factorisation exacte de est inutile, car elle est généralement irréductible. Il existe plusieurs définitions possibles de ce que l'on peut appeler une factorisation numérique de$

Si $et Les valeurs de étant connues, une factorisation approximative consiste à trouver un polynôme proche de qui factorise comme ci-dessus. Si l'on ne connaît pas le schéma de factorisation, identifier devient nécessaire. Par exemple, le nombre de facteurs irréductibles d'un polynôme est la nullité de sa matrice de Ruppert. Ainsi, les multiplicités peut être identifié par factorisation sans carré via le calcul numérique du PGCD et la révélation du rang sur les matrices de Ruppert.$

Plusieurs algorithmes ont été développés et mis en œuvre pour la factorisation numérique, un sujet de recherche toujours en cours.