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

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 d​ann gilt gerade d​ie 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.

Algorithmus

Der Algorithmus k​ann also w​ie 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
.

Anwendung

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.

Siehe auch

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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.