Faktorisierung von Polynomen

Ziel der Faktorisierung ist es, für ein gegebenes Polynom ${\displaystyle p(x)}$  aus einem Polynomring ${\displaystyle R[x]}$  eine endliche Menge irreduzibler Polynome ${\displaystyle p_{i}\in R[x]}$ , ${\displaystyle i=1,\dotsc ,n}$  zu finden mit

${\displaystyle p(x)=p_{1}(x)\cdot p_{2}(x)\dotsm p_{n}(x)}$ .

Die Faktoren ${\displaystyle p_{i}(x)}$  müssen dabei nicht alle verschieden sein, das heißt, die Faktoren können mit einer Vielfachheit größer als 1 in dieser Zerlegung auftauchen.

Ist der Koeffizientenring ${\displaystyle R}$  ein faktorieller Ring, dann ist nach einem Satz von Gauß auch ${\displaystyle R[x]}$  faktoriell. In diesem Fall existiert ein System von Primelementen, sodass diese Darstellung bis auf die Reihenfolge und Assoziiertheit eindeutig ist und jedes ${\displaystyle p_{i}(x)}$  ein Element des Primsystems ist. In Ringen, die nicht faktoriell sind, ist es im Allgemeinen nicht möglich, eine eindeutige Faktorisierung zu finden.

Über dem Körper der komplexen Zahlen ${\displaystyle \mathbb {C} }$  lässt sich jedes Polynom ${\displaystyle n}$ -ten Grades als Produkt von genau ${\displaystyle n}$  Linearfaktoren ${\displaystyle x-b_{i}}$ 

${\displaystyle p(x)=\sum _{k=0}^{n}a_{k}x^{k}=a_{n}\prod _{i=1}^{n}(x-b_{i})}$ 

schreiben. Dies ist eine der Aussagen des Fundamentalsatzes der Algebra. Man sagt, das Polynom zerfällt in seine Linearfaktoren. Die ${\displaystyle b_{i}}$  sind genau die Nullstellen der zugehörigen Polynomfunktion.

Manche Polynome lassen sich als Produkt einfacherer Polynome kleineren Grades schreiben. Beispielsweise ergibt sich durch Ausklammern und Anwendung einer binomischen Formel die Zerlegung

${\displaystyle x^{4}-4x^{2}=x^{2}\left(x^{2}-4\right)=x^{2}(x+2)(x-2)}$ .

Die Faktoren ${\displaystyle x}$  (tritt zweifach auf), ${\displaystyle x+2}$  und ${\displaystyle x-2}$  lassen sich nicht weiter zerlegen: Sie sind irreduzibel. Das Polynom ${\displaystyle x^{2}-4}$  ist zwar ein Teiler des gegebenen Polynoms, aber es lässt sich selbst noch weiter zerlegen.

Ob ein Polynom irreduzibel ist oder sich noch weiter faktorisieren lässt, hängt vom betrachteten Definitionsbereich seiner Koeffizienten ab: So lässt sich ${\displaystyle x^{2}-2}$  in den rationalen Zahlen nicht weiter zerlegen, in den reellen Zahlen hat es die Faktorisierung ${\displaystyle x^{2}-2=\left(x+{\sqrt {2}}\right)\left(x-{\sqrt {2}}\right)}$ . Ein weiteres Beispiel ist das Polynom ${\displaystyle x^{2}+1}$ : In den reellen Zahlen ist es irreduzibel, in den komplexen Zahlen gilt hingegen ${\displaystyle x^{2}+1=(x+\mathrm {i} )(x-\mathrm {i} )}$  mit der imaginären Einheit ${\displaystyle \mathrm {i} }$ .

Allgemein gilt: Hat ein Polynom ${\displaystyle p(x)}$  eine Nullstelle ${\displaystyle a}$ , so ist es ohne Rest durch ${\displaystyle (x-a)}$  teilbar, das heißt, es gilt

${\displaystyle p(x)=q(x)(x-a)}$ 

mit einem Polynom ${\displaystyle q(x)}$ , dessen Grad um eins kleiner ist und das z. B. durch Polynomdivision oder mit dem Horner-Schema berechnet werden kann. Hat nun ${\displaystyle q(x)}$  wieder eine Nullstelle, dann lässt sich diese wiederum als Linearfaktor abspalten. Da in den komplexen Zahlen nach dem Fundamentalsatz der Algebra ein nichtkonstantes Polynom stets eine Nullstelle besitzt, führt bei komplexer Rechnung dieses Vorgehen schließlich zu einer Faktorisierung durch Zerlegung in Linearfaktoren.

Ein reelles Polynom hat dagegen nicht immer eine reelle Nullstelle. Es lässt sich jedoch als komplexes Polynom mit reellen Koeffizienten auffassen. Als solches zerfällt es in Linearfaktoren und besitzt zusätzlich die Eigenschaft, dass mit jeder Nullstelle ${\displaystyle a\in \mathbb {C} }$  auch die konjugiert komplexe Zahl ${\displaystyle {\overline {a}}}$  eine Nullstelle ist. Die beiden zugehörigen Linearfaktoren ${\displaystyle (x-a)(x-{\overline {a}})}$  lassen sich zu dem reellen quadratischen Polynom

${\displaystyle x^{2}-(a+{\overline {a}})x+a{\overline {a}}=x^{2}-2\operatorname {Re} (a)x+|a|^{2}}$ 

zusammenfassen. Damit ist gezeigt, dass sich in den reellen Zahlen jedes Polynom in ein Produkt aus linearen und quadratischen Faktoren zerlegen lässt. Zum Beispiel hat das Polynom ${\displaystyle x^{3}-3x^{2}+7x-5}$  die reelle Nullstelle ${\displaystyle a_{1}=1}$  und die konjugiert komplexen Nullstellen ${\displaystyle a_{2,3}=1\pm 2\mathrm {i} }$ . In den reellen Zahlen lautet seine Faktorisierung ${\displaystyle (x-1)\left(x^{2}-2x+5\right)}$ .

Für Polynome mit ganzzahligen Koeffizienten existieren verschiedene Irreduzibilitätskriterien, wie zum Beispiel das Eisensteinkriterium, um festzustellen, ob sie in ${\displaystyle \mathbb {Q} [x]}$  irreduzibel sind. Die Bestimmung der rationalen Nullstellen eines Polynoms

${\displaystyle a_{n}x^{n}+a_{n-1}x^{n-1}+\dotsb +a_{1}x+a_{0}\in \mathbb {Z} [x]}$ 

lässt sich algorithmisch in endlich vielen Schritten lösen, denn für jede Nullstelle ${\displaystyle {\tfrac {a}{b}}\in \mathbb {Q} }$  gilt, dass ${\displaystyle a}$  ein Teiler von ${\displaystyle a_{0}}$  und ${\displaystyle b}$  ein Teiler von ${\displaystyle a_{n}}$  ist (siehe Satz über rationale Nullstellen).

Beispielsweise findet man bei dem Polynom ${\displaystyle 3x^{5}-5x^{4}-6x+10}$  durch Ausprobieren aller Möglichkeiten die rationale Nullstelle ${\displaystyle {\tfrac {5}{3}}}$ . Polynomdivision ergibt

${\displaystyle \left(3x^{5}-5x^{4}-6x+10\right):\left(x-{\tfrac {5}{3}}\right)=3\left(x^{4}-2\right)}$ 

und das Polynom ${\displaystyle x^{4}-2}$  ist nach dem Eisensteinkriterium (mit der Primzahl 2) irreduzibel, so dass sich schließlich die ganzzahlige Faktorisierung

${\displaystyle 3x^{5}-5x^{4}-6x+10=\left(x^{4}-2\right)(3x-5)}$ 

ergibt.

B. A. Hausmann beschrieb 1937 eine Anwendung des Algorithmus von Kronecker. Elwyn Berlekamp veröffentlichte 1967 den Berlekamp-Algorithmus, mit dem Polynome über dem Restklassenkörper ${\displaystyle \mathbb {F} _{p}}$  faktorisiert werden können. 1992 entdeckte Harald Niederreiter eine weitere Möglichkeit, Polynome über endlichen Körpern zu faktorisieren, auf ihn geht der Niederreiter-Algorithmus zurück.

• Online-Tool zum Faktorisieren