Wichtiger Hinweis zum Inhalt des Online-LexikonsBei den auf dieser Seite aufgeführten Texten/Artikeln/Inhalten handelt es sich ausschließlich um fremde Inhalte, die sich die Aschendorff Verlag GmbH & Co. KG ausdrücklich nicht zu Eigen macht. Diese fremden Inhalte, die keiner regelmäßigen Überprüfung unterliegen, sind ausnahmslos solche der freien Enzyklopädie Wikipedia, für die keinerlei Verantwortung übernommen wird.

---

Lizenzbestimmungen Der Text/Artikel/Inhalt auf dieser Seite innerhalb der Rubrik "Online Lexikon" basiert, soweit nicht anders angegeben, auf dem Artikel Berlekamp-Algorithmus aus der freien Enzyklopädie Wikipedia. Die Inhalte stehen unter der GNU Lizenz für freie Dokumentation. Eine Liste der Autoren ist dort abrufbar.

Faktorisierung von Polynomen

In der Algebra können analog zur Primfaktorzerlegung von ganzen_Zahlen auch Polynome in Faktoren zerlegt werden.

Dabei versucht man, für ein gegebenes Polynom $p$ aus einem Polynomring $R$ eine endliche Menge $\backslash lbrace\; p\_1,\; ...,\; p\_n\; \backslash rbrace\; \backslash subseteq\; R$ zu finden, sodass $p\; =\; \backslash prod\_\{i=1\}^n\; p\_i$.

In einem faktoriellen_Ring existiert dabei ein Primsystem, sodass diese Darstellung bis auf die Reihenfolge und _Assoziiertheit eindeutig ist und jedes $p\_i$ ein Element des Primsystems ist.
In Ringen, die nicht faktoriell sind, ist es im Allgemeinen nicht möglich, eine eindeutige Faktorisierung zu finden.

Über einem algebraisch abgeschlossenen Körpern $\backslash mathbb\{K\}$, wie etwa den komplexen_Zahlen ergibt sich jedes Polynom als Produkt von Linearfaktoren. Man sagt, das Polynom zerfällt in seine Linearfaktoren.

Ist $p$ ein Polynom mit mit $a\_k\; \backslash in\; \backslash mathbb\{K\}$, so gibt es eine Darstellung    $p\; =\; \backslash sum\_\{k=0\}^n\; a\_k\; X^k\; =\backslash prod\_\{i=1\}^n\; (X\; -\; b\_i)$


D.h, das Polynom zerfällt in genau $n$ Faktoren der Form $X-b\_i$.
Die $b\_i$ sind dabei genau die Nullstellen der zugehörigen Polynomfunktion.

Die algebraisch abgeschlossenen komplexen Zahlen sind eine Körpererweiterung der Dimension 2 über den reellen_Zahlen. Daher lassen sich Polynome aus $\backslash mathbb\{R\}[X]$ (der Polynomring über den reellen Zahlen) als Produkt von quadratischen und linearen Faktoren darstellen.

Beispiele

* Das Polynom $x^2\; -\; 1$ hat die Nullstellen $-1,\backslash ,\; 1$ und damit die Faktorisierung
*:$x^2\; -\; 1\; =\; (x+1)\backslash cdot(x-1)$
* Das Polynom $x^2+1$ hat die komplexen Nullstellen $-\backslash mathrm\{i\},\backslash ,\backslash mathrm\{i\}$ und damit die Faktorisierung
*:$x^2\; +\; 1\; =\; (x+\backslash mathrm\{i\})\backslash cdot(x-\backslash mathrm\{i\})$

Algorithmen

Elwyn Ralph Berlekamp veröffentlichte 1967 den Berlekamp-Algorithmus mit dem Polynome über dem Restklassenkörper $\backslash mathbb\{F\}\_p$ faktorisiert werden können.

       VIDEO-NEWS UND ANGEBOTE