Berlekamp-Algorithmus

Teilweise Übersetzung aus en:Berlekamp's algorithm

Dieser Artikel behandelt den Algorithmus zur Faktorisierung von Polynomen über einen endliche Körper. Den Algorithmus zur Suche des kürzesten linear rückgekoppelten Schieberegisters findet man unter Berlekamp-Massey-Algorithmus.

In der Computeralgebra einen Teilgebiet der Mathematik ist der Berlekamp-Algorithmus eine Methode zur Faktorisierung von Polynomen über einen endlichen Körper, die 1967 von Elwyn Berlekamp entwickelt wurde. Er ist in den meißten Computer-Algebra-Systemen 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 $P(x)\in \mathbb {F} _{q}$ mit $\deg P(x)=n$in irreduzible Faktoren $p_{1}(x)\cdot \dots \cdot p_{r}(x)=P(x)$ wobei die Größe r unbekannt ist und auch eins sein kann, wenn $P(x)$ irreduzibel ist. Dabei kann man ohne Beschränkung der Allgemeinheit annehmen dass $P(x)$ quadratfrei ist.

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

$P(x)=p_{1}(x)\cdot \dots \cdot p_{r}(x)=\prod _{a\in \mathbb {F} _{q}}\gcd(P(x),b(x)-a).$

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

Weil G(x) durch P(x) teilbar ist, sucht man also b(x), die die Kongurenz $b(x)^{q}\equiv b(x)\mod P(x)$ erfüllen.

Man kann nun beweisen, dass alle diese b(x) Eigenvektoren einer Matrix ${\mathcal {Q}}=[q_{k,l}]$ zum Eigenwert 1 sind, wobei die $q_{k,l}$ gegeben sind durch die Kongurenz:

$x^{iq}\equiv q_{n,i}x^{n}+q_{n-1,i}x^{n-1}+\ldots +q_{0,i}{\pmod {P(x)}}$.

Denn dann gilt: $b(x)=\sum _{j}b_{j}x^{j}{\stackrel {Eigenvektor}{=}}\sum _{j}{\bigl (}q_{j,l}b_{l}{\bigr )}x^{j}=\sum _{l}b_{l}\sum _{j}q_{j,l}x^{j}\equiv \sum _{l}b_{l}x^{lq}{\stackrel {\mathbb {F} _{q}}{=}}\sum _{l}b_{l}^{q}x^{lq}{\stackrel {\mathbb {F} _{q}}{=}}{{\bigl (}\sum _{l}b_{l}x^{l}{\bigr )}}^{q}=b^{q}\mod P(x)$.

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

Algorithmus

Der Algorithmus kann also wie folgt zusammengefasst werden:

• man berechnet ${\mathcal {Q}}$, in dem man für $i=0,\dots ,n$ jeweils $x^{iq}\mod P(x)$ reduziert
• man bestimmt die Eigenvektoren $b^{(j)}$ von ${\mathcal {Q}}$
• solange noch nicht alle $r=\operatorname {rang} ({\mathcal {Q}}-{\mathcal {I}})$ Faktoren von $P(x)$ bestimmt sind berechne für alle $b^{(j)}\neq (0,\dots ,0)$ und für alle $a\in \mathbb {F} _{q}$

$\gcd(P(x),b^{(j)}(x)-a)$

Anwendung

Eine wichtige Anwendung des Berlekamp-Algoritmus ist die Berechnung des diskreten Logarithmus über einen endlichen Körper $\mathbb {F} _{p^{n}}$ mit Primzahl $p$ und $n\geq 2$. Was eine große Bedeutung in der Public Key Cryptography hat. In einen endlichen Körper, ist die schnellste Methode zur Berechnung des diskreten Logarithmus der Index-Calculus-Algorithmus, bei dem Körperelemente faktorisiert werden. Da $\mathbb {F} _{p^{n}}$ isomorph ist zu einem Polynomring über $\mathbb {F} _{p}$ faktorisiert nach einem irreduziblen Polynom vom Grad n, entspricht die Faktorisierung der Körperelemente in $\mathbb {F} _{p^{n}}$ der Faktorisierung von Polynomen in einem Polynomring über $\mathbb {F} _{p}$ faktorisiert nach einem irreduziblen Polynom vom Grad n. Diese kann dann mit dem Berlekamp-Algorithmus durchführ werden.

Siehe auch

• Faktorisierung von Polynomen
• Cantor-Zassenhaus Algorithmus

Quellen

• Atilla Pethö: Algebraische Algorithtmen. 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". Bell Systems Technical Journal, 46:1853-1859, 1967. bzw. in: Elwyn R. Berlekamp. "Algebraic Coding Theory". Mc-Graw Hill, 1968.