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.

Hintergrund

Bearbeiten

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

Algorithmus

Bearbeiten

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  
 .

Anwendung

Bearbeiten

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

Bearbeiten

Literatur

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