imported>Ulricus Angelus: /* growthexperiments-addlink-summary-summary:1|0|0 */

2025-05-31T12:27:11Z

growthexperiments-addlink-summary-summary:1|0|0

Neue Seite

{{Dieser Artikel|behandelt den Algorithmus zur Faktorisierung von Polynomen über einem endlichen Körper. Den Algorithmus zur Suche des kürzesten [[Linear rückgekoppeltes Schieberegister|linear rückgekoppelten Schieberegisters]] findet man unter [[Berlekamp-Massey-Algorithmus]].}}

In der [[Computeralgebra]], einem Teilgebiet der [[Mathematik]], ist der '''Berlekamp-Algorithmus''' eine Methode zur Faktorisierung von [[Polynom]]en über einem [[Endlicher Körper|endlichen Körper]], die 1967 von [[Elwyn Berlekamp]] entwickelt wurde. Er ist in den meisten [[Computeralgebrasystem]]en implementiert und war der führende Faktorisierungsalgorithmus bis zur Entwicklung des [[Cantor-Zassenhaus-Algorithmus]], einer [[Probabilistischer Algorithmus|probabilistischen]] Variante des Berlekamp-Algorithmus aus dem Jahre 1981.

== Hintergrund ==
Gesucht ist eine Faktorisierung von <math> P(x) \in \mathbb{F}_q[x]</math> mit <math>\deg P(x)=n</math> in irreduzible Faktoren <math> p_1(x)\cdots p_r(x)=P(x)</math> wobei die Größe <math>r</math> unbekannt ist. Insbesondere kann auch <math>r=1</math> gelten, nämlich wenn <math>P(x)</math> [[Irreduzibles Polynom|irreduzibel]] ist. Dabei kann man [[ohne Beschränkung der Allgemeinheit]] annehmen, dass <math> P(x) </math> [[quadratfrei]] ist, weil quadratfreie Polynome <math> P(x) </math> die Eigenschaft <math> \operatorname{ggT}(P(x), P'(x))=1 </math> erfüllen und bei nicht quadratfreien Polynomen auf diese Weise bereits ein echter Teiler gefunden wird. (<math> P'(x) </math> bezeichnet hier die formale Ableitung nach <math>x</math> und <math> \operatorname{ggT} </math> den [[GgT|größten gemeinsamen Teiler]].)

Um die <math>p_i</math> zu bestimmen, bedient man sich eines leichter zu faktorisierenden Polynoms <math>\textstyle G(x):= \prod_{a \in \mathbb{F}_q} \bigl( b(x) - a \bigr)</math>, das von <math>P(x)</math> geteilt wird, denn dann gilt
:<math> P(x) =p_1(x)\cdots p_r(x)= \prod_{a \in \mathbb{F}_q} \operatorname{ggT}(P(x),b(x)-a).</math>

Da <math>\mathbb{F}_q</math> ein [[endlicher Körper]] ist, kann man in der Identität <math>\textstyle X^q-X=\prod_{a \in \mathbb{F}_q} (X-a)</math> das <math>X</math> durch <math>b(x)</math> ersetzen und erhält <math>\textstyle G(x)=\prod_{a \in \mathbb{F}_q} \bigl( b(x) - a \bigr)=b(x)^q-b(x) </math>.

Damit <math>G(x)</math> tatsächlich von <math>P(x)</math> geteilt wird, sucht man ein <math>b(x)</math>, welches die Kongruenz <math>b(x)^q \equiv b(x) \mod P(x)</math> erfüllt.

Man kann nun beweisen, dass alle [[Eigenvektoren]] <math> \vec b = (b_0,\dots,b_{n-1})^\operatorname{T}</math> einer bestimmten <math>n \times n</math> Matrix <math>\mathcal{Q}=[q_{k,l}]</math> zum Eigenwert 1 jeweils solch ein <math>b(x) := \sum_i b_ix^i</math> liefern, wobei die <math>q_{k,l}</math> gegeben sind durch die Kongruenzen:
:<math>x^{iq} \equiv q_{n-1,i}x^{n-1} + \cdots + q_{1,i}x + q_{0,i} \pmod{P(x)} \quad \text{ mit } i=0,\dots,n-1</math>.

Denn dann gilt gerade die Kongruenz:
:<math>b(x)^q = {\bigl( \sum_l b_l x^l \bigr)}^q \stackrel{\mathbb{F}_q}{{}={}} \sum_l b_l^q x^{lq} \stackrel{\mathbb{F}_q}{{}={}} \sum_l b_l x^{lq} \underset{\operatorname{mod} P(x)} {{}\equiv{}} \sum_l b_l \sum_j q_{j,l} x^j = \sum_j \bigl(\sum_l q_{j,l} b_l \bigr) x^j \stackrel{\,\mathrm{Eigenvektor}\,}{{}={}} \sum_j b_j x^j = b(x) </math>.

Man bestimmt also alle Eigenvektoren <math>b^{(j)}</math> von <math>\mathcal{Q}</math> und erhält dann die <math>p_i(x)</math>, indem man für alle <math>a \in \mathbb{F}_q</math> und für alle Eigenvektoren <math>b^{(j)}</math> den <math>\operatorname{ggT}(P(x),b^{(j)}(x)-a)</math> berechnet. Dabei kann man zum einen den trivialen Eigenvektor <math>(0,\dots,0)</math> auslassen und zum anderen die Berechnungen beenden, wenn man <math>r=\operatorname{rang} ( \mathcal Q - \mathcal I )</math> verschiedene Faktoren gefunden hat.

== Algorithmus ==
Der Algorithmus kann also wie folgt zusammengefasst werden:
* Man berechnet <math>\mathcal{Q}</math>, indem man für <math>i=0,\ldots,n-1</math> jeweils <math>x^{iq} \mod P(x)</math> reduziert.
* Man bestimmt eine Basis <math>b^{(j)}</math> des Eigenraums von <math>\mathcal{Q}</math> zum Eigenwert 1.
* Solange noch nicht alle <math>r=\operatorname{rang} ( \mathcal Q - \mathcal I )</math> Faktoren von <math>P(x)</math> bestimmt sind, berechne für alle <math>b^{(j)} \neq (0,\dots,0)</math> und für alle <math>a \in \mathbb{F}_q</math>
:<math>\operatorname{ggT}(P(x),b^{(j)}(x)-a)</math>.

== Anwendung ==
Eine wichtige Anwendung des Berlekamp-Algorithmus ist die Berechnung des [[Diskreter Logarithmus|diskreten Logarithmus]] über einem endlichen Körper <math>\mathbb{F}_{p^n}</math> mit Primzahl <math>p</math> und <math>n\geq 2</math>, was eine große Bedeutung in der [[Asymmetrisches Kryptosystem|Public Key Cryptography]] hat. In einem endlichen Körper ist die schnellste Methode zur Berechnung des diskreten Logarithmus der [[Index-Calculus-Algorithmus]], bei dem Körperelemente faktorisiert werden. Da <math>\mathbb{F}_{p^n}</math> isomorph ist zu einem Polynomring über <math>\mathbb{F}_{p}</math>, faktorisiert nach einem irreduziblen Polynom vom Grad <math>n</math>, entspricht die Faktorisierung der Körperelemente in <math>\mathbb{F}_{p^n}</math> der Faktorisierung von Polynomen in einem Polynomring über <math>\mathbb{F}_{p}</math>, faktorisiert nach einem irreduziblen Polynom vom Grad <math>n</math>. Diese kann dann mit dem Berlekamp-Algorithmus durchgeführt werden.

== Siehe auch ==
* [[Faktorisierung von Polynomen]]

== Literatur ==
* {{Literatur
|Autor=Atilla Pethö
|Hrsg=Michael Pohst
|Titel=Algebraische Algorithmen
|Verlag=Vieweg
|Ort=
|Datum=1999
|ISBN=978-3-528-06598-0
|Seiten=183}}
* {{Literatur
|Autor=Michael Kaplan
|Titel=Computeralgebra
|Verlag=Springer
|Ort=
|Datum=2005
|ISBN=3-540-21379-1
|Seiten=239}}
* Elwyn R. Berlekamp: ''Factoring Polynomials Over Finite Fields''. In: ''Bell System Technical Journal'', Band 46, 1967, S. 1853–1859 bzw. in: Elwyn R. Berlekamp: ''Algebraic Coding Theory''. Mc-Graw Hill, 1968.

[[Kategorie:Algebra]]
[[Kategorie:Faktorisierungsverfahren]]

Berlekamp-Algorithmus - Versionsgeschichte

imported>Ulricus Angelus: /* growthexperiments-addlink-summary-summary:1|0|0 */