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.
Gesucht ist eine Faktorisierung von
mit
in irreduzible Faktoren
wobei die Größe
unbekannt ist. Insbesondere kann auch
gelten, nämlich wenn
irreduzibel ist. Dabei kann man ohne Beschränkung der Allgemeinheit annehmen, dass
quadratfrei ist, weil quadratfreie Polynome
die Eigenschaft
erfüllen und bei nicht quadratfreien Polynomen auf diese Weise bereits ein echter Teiler gefunden wird. (
bezeichnet hier die formale Ableitung nach
und
den größten gemeinsamen Teiler.)
Um die
zu bestimmen, bedient man sich eines leichter zu faktorisierenden Polynoms
, das von
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).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c16cd453b085886c9ec84462c661b3c597311688)
Da
ein endlicher Körper ist, kann man in der Identität
das
durch
ersetzen und erhält
.
Damit
tatsächlich von
geteilt wird, sucht man ein
, welches die Kongruenz
erfüllt.
Man kann nun beweisen, dass alle Eigenvektoren
einer bestimmten
Matrix
zum Eigenwert 1 jeweils solch ein
liefern, wobei die
gegeben sind durch die Kongruenzen:
.
Denn dann gilt gerade die Kongruenz:
.
Man bestimmt also alle Eigenvektoren
von
und erhält dann die
, indem man für alle
und für alle Eigenvektoren
den
berechnet. Dabei kann man zum einen den trivialen Eigenvektor
auslassen und zum anderen die Berechnungen beenden, wenn man
verschiedene Faktoren gefunden hat.
Der Algorithmus kann also wie folgt zusammengefasst werden:
- Man berechnet
, indem man für
jeweils
reduziert. - Man bestimmt eine Basis
des Eigenraums von
zum Eigenwert 1. - Solange noch nicht alle
Faktoren von
bestimmt sind, berechne für alle
und für alle ![{\displaystyle a\in \mathbb {F} _{q}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fc15829f59b5824930672b9e4c29c38144ecf83a)
.
Eine wichtige Anwendung des Berlekamp-Algorithmus ist die Berechnung des diskreten Logarithmus über einem endlichen Körper
mit Primzahl
und
, 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
isomorph ist zu einem Polynomring über
, faktorisiert nach einem irreduziblen Polynom vom Grad
, entspricht die Faktorisierung der Körperelemente in
der Faktorisierung von Polynomen in einem Polynomring über
, faktorisiert nach einem irreduziblen Polynom vom Grad
. Diese kann dann mit dem Berlekamp-Algorithmus durchgeführt werden.
- 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.