Berlekamp-Algorithmus

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.

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

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.

• Faktorisierung von Polynomen

• 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.