BerlekampVerfahren

Berlekamp-Verfahren, auch Berlekamp-Algorithmus genannt, ist ein Verfahren der algebraischen Zahlentheorie zur Faktorisierung von Polynomen über endlichen Körpern. Es dient dazu, ein gegebenes Polynom f(x) ∈ F_p[x] in irreduzible Faktoren zu zerlegen und bildet eine klassische Methode in der computergestützten Algebra.

Der Kern des Verfahrens liegt in der Bestimmung eines Berlekamp-Raums, der auf dem Frobenius-Abbild h(x) → h(x)^p modulo f basiert. Man betrachtet den Quotientenring F_p[x] / (f) als Vektorraum der Dimension gleich dem Grad von f. Die Abbildung durch H(x) = x^p modulo f liefert eine lineare Transformation in diesem Raum. Die Nullspace-Basis dieser Transformation – der Berlekamp-Raum – besteht aus Polynomen h, die h(x)^p ≡ h(x) (mod f). Aus nichttrivialen Polynomen dieses Raums lassen sich Faktoren von f ableiten: Wählt man eine Linearkombination g(x) der Basis, erhält man durch gcd(f, g) einen Nichttrivialfaktor. Reicht man diesen Faktor aus und setzt den Zerlegungsprozess fort, bis f vollständig faktorisiert ist.

In der Praxis wird der Berlekamp-Schritt häufig durch weitere Zerlegungsmethoden ergänzt, etwa Cantor-Zassenhaus, um das Polynom vollständig in irreduzible Faktoren zu zerlegen. Das Verfahren ist besonders verständlich für Polynome über endliche Körper und bildet eine fundamentale Methode in der faktorisierenden Algebra. Es wird in Computeralgebra-Systemen verwendet und dient zudem als Grundlage für weiterführende Faktorisierungsverfahren in der Theorie der endlichen Felder.