Faktorisierung von Polynomen

Grundidee und Ziel

Die Faktorisierung von Polynomen ist in der Algebra die Zerlegung eines Polynoms in ein Produkt aus irreduziblen Polynomen. Sie ist damit analog zur Primfaktorzerlegung ganzer Zahlen. Ein irreduzibles Polynom ist ein Polynom, das sich im betrachteten Polynomring nicht weiter in Polynome kleineren Grades zerlegen lässt.

Für ein gegebenes Polynom p(x) aus einem Polynomring R[x] sucht man eine endliche Menge irreduzibler Polynome p_i in R[x] mit i = 1, ..., n, sodass gilt: p(x)=p_1(x)·p_2(x)·...·p_n(x). Die Faktoren müssen nicht alle verschieden sein; ein Faktor kann also mit einer Vielfachheit größer als 1 auftreten.

Eindeutigkeit und komplexe Zahlen

Ob eine Faktorisierung eindeutig ist, hängt vom Koeffizientenring R ab. Ist R ein faktorieller Ring, dann ist nach einem Satz von Gauß auch R[x] faktoriell. Dann gibt es ein System von Primelementen, und die Darstellung ist bis auf Reihenfolge und Assoziiertheit eindeutig. Jeder Faktor p_i(x) ist dann ein Element dieses Primsystems. In Ringen, die nicht faktoriell sind, gibt es im Allgemeinen keine eindeutige Faktorisierung.

Über dem Körper der komplexen Zahlen C lässt sich jedes Polynom n-ten Grades als Produkt von genau n Linearfaktoren x-b_i schreiben: p(x)=sum_{k=0}^{n} a_k x^k = a_n prod_{i=1}^{n}(x-b_i). Dies ist eine Aussage des Fundamentalsatzes der Algebra. Man sagt, das Polynom zerfällt in seine Linearfaktoren. Die Zahlen b_i sind genau die Nullstellen der zugehörigen Polynomfunktion.

Nullstellen und Linearfaktoren

Ein einfaches Beispiel ist x^4-4x^2. Durch Ausklammern und Anwendung einer binomischen Formel erhält man x^4-4x^2 = x^2(x^2-4)=x^2(x+2)(x-2). Die Faktoren x, x+2 und x-2 sind irreduzibel; x tritt dabei zweifach auf. Das Polynom x^2-4 ist zwar ein Teiler, aber noch nicht vollständig zerlegt.

Ob ein Polynom irreduzibel ist, hängt vom betrachteten Zahlenbereich ab. Das Polynom x^2-2 ist über den rationalen Zahlen nicht weiter zerlegbar, über den reellen Zahlen aber x^2-2=(x+sqrt(2))(x-sqrt(2)). Das Polynom x^2+1 ist über den reellen Zahlen irreduzibel, über den komplexen Zahlen gilt x^2+1=(x+i)(x-i), wobei i die imaginäre Einheit ist.

Hat ein Polynom p(x) eine Nullstelle a, dann ist es ohne Rest durch x-a teilbar. Es gilt p(x)=q(x)(x-a), wobei q(x) ein Polynom ist, dessen Grad um eins kleiner ist. q(x) kann zum Beispiel durch Polynomdivision oder mit dem Horner-Schema berechnet werden. Hat q(x) wieder eine Nullstelle, kann erneut ein Linearfaktor abgespalten werden. Über den komplexen Zahlen führt dieses Verfahren wegen des Fundamentalsatzes der Algebra schließlich zur vollständigen Zerlegung in Linearfaktoren.

Reelle Polynome

Ein reelles Polynom hat nicht immer eine reelle Nullstelle. Man kann es aber als komplexes Polynom mit reellen Koeffizienten auffassen. Dann zerfällt es über den komplexen Zahlen in Linearfaktoren. Zusätzlich gilt: Wenn a eine komplexe Nullstelle ist, dann ist auch die konjugiert komplexe Zahl overline(a) eine Nullstelle.

Die beiden zugehörigen Linearfaktoren (x-a)(x-overline(a)) lassen sich zu einem reellen quadratischen Polynom zusammenfassen: x^2-(a+overline(a))x+a overline(a)=x^2-2 Re(a)x+|a|^2. Daraus folgt, dass sich jedes Polynom über den reellen Zahlen in ein Produkt aus linearen und quadratischen Faktoren zerlegen lässt.

Ein Beispiel ist x^3-3x^2+7x-5. Es hat die reelle Nullstelle a_1=1 und die konjugiert komplexen Nullstellen a_{2,3}=1±2i. Über den reellen Zahlen lautet seine Faktorisierung (x-1)(x^2-2x+5).

Rationale und ganzzahlige Polynome

Für Polynome mit ganzzahligen Koeffizienten gibt es Irreduzibilitätskriterien, zum Beispiel das Eisensteinkriterium. Damit kann man prüfen, ob ein Polynom in Q[x] irreduzibel ist.

Die rationalen Nullstellen eines Polynoms a_n x^n + a_{n-1}x^{n-1}+...+a_1x+a_0 in Z[x] lassen sich algorithmisch in endlich vielen Schritten bestimmen. Nach dem Satz über rationale Nullstellen gilt für jede Nullstelle a/b in Q: a ist ein Teiler von a_0 und b ist ein Teiler von a_n.

Beim Polynom 3x^5-5x^4-6x+10 findet man durch Ausprobieren aller Möglichkeiten die rationale Nullstelle 5/3. Polynomdivision ergibt (3x^5-5x^4-6x+10):(x-5/3)=3(x^4-2). Das Polynom x^4-2 ist nach dem Eisensteinkriterium mit der Primzahl 2 irreduzibel. Damit ergibt sich die ganzzahlige Faktorisierung 3x^5-5x^4-6x+10=(x^4-2)(3x-5).

Algorithmen

Für die Faktorisierung von Polynomen gibt es spezielle Algorithmen. 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 F_p faktorisiert werden können. Harald Niederreiter entdeckte 1992 eine weitere Möglichkeit zur Faktorisierung von Polynomen über endlichen Körpern; darauf geht der Niederreiter-Algorithmus zurück.