Berlekamp-Algorithmus

Dieser Artikel behandelt den Algorithmus zur Faktorisierung von Polynomen über einem endlichen Körper. Den Algorithmus zur Suche des kürzesten 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 Polynomen über einem endlichen Körper, die 1967 von Elwyn Berlekamp entwickelt wurde. Er ist in den meisten Computeralgebrasystemen implementiert und war der führende Faktorisierungsalgorithmus bis zur Entwicklung des Cantor-Zassenhaus-Algorithmus, einer probabilistischen Variante des Berlekamp-Algorithmus aus dem Jahre 1981.

Hintergrund

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

Um die ${\displaystyle p_{i}}$ zu bestimmen, bedient man sich eines leichter zu faktorisierenden Polynoms ${\displaystyle \textstyle G(x):=\prod _{a\in \mathbb {F} _{q}}{\bigl (}b(x)-a{\bigr )}}$, das von ${\displaystyle P(x)}$ geteilt wird, denn dann gilt

${\displaystyle P(x)=p_{1}(x)\cdots p_{r}(x)=\prod _{a\in \mathbb {F} _{q}}\operatorname {ggT} (P(x),b(x)-a).}$

Da ${\displaystyle \mathbb {F} _{q}}$ ein endlicher Körper ist, kann man in der Identität ${\displaystyle \textstyle X^{q}-X=\prod _{a\in \mathbb {F} _{q}}(X-a)}$ das ${\displaystyle X}$ durch ${\displaystyle b(x)}$ ersetzen und erhält ${\displaystyle \textstyle G(x)=\prod _{a\in \mathbb {F} _{q}}{\bigl (}b(x)-a{\bigr )}=b(x)^{q}-b(x)}$.

Damit ${\displaystyle G(x)}$ tatsächlich von ${\displaystyle P(x)}$ geteilt wird, sucht man ein ${\displaystyle b(x)}$, welches die Kongruenz ${\displaystyle b(x)^{q}\equiv b(x)\mod P(x)}$ erfüllt.

Man kann nun beweisen, dass alle Eigenvektoren ${\displaystyle {\vec {b}}=(b_{0},\dots ,b_{n-1})^{\operatorname {T} }}$ einer bestimmten ${\displaystyle n\times n}$ Matrix ${\displaystyle {\mathcal {Q}}=[q_{k,l}]}$ zum Eigenwert 1 jeweils solch ein ${\displaystyle b(x):=\sum _{i}b_{i}x^{i}}$ liefern, wobei die ${\displaystyle q_{k,l}}$ gegeben sind durch die Kongruenzen:

${\displaystyle 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}$.

Denn dann gilt gerade die Kongruenz:

${\displaystyle 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)}$.

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

Algorithmus

Der Algorithmus kann also wie folgt zusammengefasst werden:

• Man berechnet ${\displaystyle {\mathcal {Q}}}$, indem man für ${\displaystyle i=0,\ldots ,n-1}$ jeweils ${\displaystyle x^{iq}\mod P(x)}$ reduziert.
• Man bestimmt eine Basis ${\displaystyle b^{(j)}}$ des Eigenraums von ${\displaystyle {\mathcal {Q}}}$ zum Eigenwert 1.
• Solange noch nicht alle ${\displaystyle r=\operatorname {rang} ({\mathcal {Q}}-{\mathcal {I}})}$ Faktoren von ${\displaystyle P(x)}$ bestimmt sind, berechne für alle ${\displaystyle b^{(j)}\neq (0,\dots ,0)}$ und für alle ${\displaystyle a\in \mathbb {F} _{q}}$

${\displaystyle \operatorname {ggT} (P(x),b^{(j)}(x)-a)}$.

Anwendung

Eine wichtige Anwendung des Berlekamp-Algorithmus ist die Berechnung des diskreten Logarithmus über einem endlichen Körper ${\displaystyle \mathbb {F} _{p^{n}}}$ mit Primzahl ${\displaystyle p}$ und ${\displaystyle n\geq 2}$, was eine große Bedeutung in der 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 ${\displaystyle \mathbb {F} _{p^{n}}}$ isomorph ist zu einem Polynomring über ${\displaystyle \mathbb {F} _{p}}$, faktorisiert nach einem irreduziblen Polynom vom Grad ${\displaystyle n}$, entspricht die Faktorisierung der Körperelemente in ${\displaystyle \mathbb {F} _{p^{n}}}$ der Faktorisierung von Polynomen in einem Polynomring über ${\displaystyle \mathbb {F} _{p}}$, faktorisiert nach einem irreduziblen Polynom vom Grad ${\displaystyle n}$. Diese kann dann mit dem Berlekamp-Algorithmus durchgeführt werden.

Siehe auch

• Faktorisierung von Polynomen

Literatur

• Atilla Pethö: Algebraische Algorithmen. Hrsg.: Michael Pohst. Vieweg, 1999, ISBN 978-3-528-06598-0, S. 183.
• Michael Kaplan: Computeralgebra. Springer, 2005, ISBN 3-540-21379-1, S. 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.