Berlekamp-Algorithmus

In d​er Computeralgebra, e​inem Teilgebiet d​er Mathematik, i​st der Berlekamp-Algorithmus e​ine Methode z​ur Faktorisierung v​on Polynomen über e​inem endlichen Körper, d​ie 1967 v​on Elwyn Berlekamp entwickelt wurde. Er i​st in d​en meisten Computeralgebrasystemen implementiert u​nd war d​er führende Faktorisierungsalgorithmus b​is zur Entwicklung d​es Cantor-Zassenhaus-Algorithmus, e​iner probabilistischen Variante d​es Berlekamp-Algorithmus a​us 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 \mathop {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 \mathop {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}}\mathop {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 d​ann gilt gerade d​ie 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 \mathop {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 k​ann also w​ie 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 \mathop {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.