Berlekamp-Algorithmus

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.

Inhaltsverzeichnis

Hintergrund

Gesucht ist eine Faktorisierung von  P(x) \in \mathbb{F}_q mit deg P(x) = n in irreduzible Faktoren  p_1(x)\cdots p_r(x)=P(x) wobei die Größe r unbekannt ist und auch eins sein kann, wenn P(x) irreduzibel ist. Dabei kann man ohne Beschränkung der Allgemeinheit annehmen, dass P(x) quadratfrei ist, weil quadratfreie Polynome P(x) die Eigenschaft  \mathop{ggT}(P(x), P'(x))=1 erfüllen und bei nicht quadratfreien Polynomen auf diese Weise bereits ein echter Teiler gefunden wird. (P'(x) bezeichnet hier die formale Ableitung nach x und  \mathop{ggT} den größten gemeinsamen Teiler.)

Um die pi zu bestimmen, bedient man sich eines leichter zu faktorisierenden Polynoms G(x):= \prod_{a \in \mathbb{F}_q} \bigl( b(x) - a \bigr), das von P(x) geteilt wird, denn dann gilt

 P(x) =p_1(x)\cdots p_r(x)= \prod_{a \in \mathbb{F}_q} \mathop{ggT}(P(x),b(x)-a).

Da \mathbb{F}_q ein endlicher Körper ist, kann man in der Identität X^q-X=\prod_{a \in \mathbb{F}_q} (X-a) X durch b(x) ersetzen und erhält G(x)=\prod_{a \in \mathbb{F}_q} \bigl( b(x) - a \bigr)=b(x)^q-b(x) .

Weil G(x) durch P(x) teilbar ist, sucht man also b(x), die die Kongruenz b(x)^q \equiv b(x) \mod P(x) erfüllen.

Man kann nun beweisen, dass alle diese b(x) Eigenvektoren einer n \times n Matrix \mathcal{Q}=[q_{k,l}] zum Eigenwert 1 sind, wobei die qk,l gegeben sind durch die Kongruenzen:

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: b(x)=\sum_j b_j x^j \stackrel{Eigenvektor}{=} \sum_j \bigl( q_{j,l} b_l \bigr) x^j = \sum_l b_l \sum_j q_{j,l} x^j \equiv \sum_l b_l x^{lq} \stackrel{\mathbb{F}_q}{=} \sum_l b_l^q x^{lq} \stackrel{\mathbb{F}_q}{=} {\bigl( \sum_l b_l x^l \bigr)}^q = b^q  \mod P(x).

Man bestimmt also alle Eigenvektoren b(j) von \mathcal{Q} und erhält dann die pi(x), indem man für alle a \in \mathbb{F}_q und für alle Eigenvektoren b(j) \mathop{ggT}(P(x),b^{(j)}(x)-a) berechnet. Dabei kann man zum einen den trivialen Eigenvektor (0,\dots,0) auslassen und zum anderen die Berechnungen beenden, wenn man r=\operatorname{rang} ( \mathcal Q - \mathcal I ) verschiedene Faktoren gefunden hat.

Algorithmus

Der Algorithmus kann also wie folgt zusammengefasst werden:

  • Man berechnet \mathcal{Q}, indem man für i=0,\ldots,n jeweils x^{iq} \mod P(x) reduziert.
  • Man bestimmt die Eigenvektoren b(j) von \mathcal{Q}.
  • Solange noch nicht alle r=\operatorname{rang} ( \mathcal Q - \mathcal I ) Faktoren von P(x) bestimmt sind, berechne für alle b^{(j)} \neq (0,\dots,0) und für alle a \in \mathbb{F}_q
\mathop{ggT}(P(x),b^{(j)}(x)-a).

Anwendung

Eine wichtige Anwendung des Berlekamp-Algorithmus ist die Berechnung des diskreten Logarithmus über einem endlichen Körper \mathbb{F}_{p^n} mit Primzahl p und 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 \mathbb{F}_{p^n} isomorph ist zu einem Polynomring über \mathbb{F}_{p}, faktorisiert nach einem irreduziblen Polynom vom Grad n, entspricht die Faktorisierung der Körperelemente in \mathbb{F}_{p^n} der Faktorisierung von Polynomen in einem Polynomring über \mathbb{F}_{p}, faktorisiert nach einem irreduziblen Polynom vom Grad n. Diese kann dann mit dem Berlekamp-Algorithmus durchgeführt werden.

Siehe auch

Quellen

  • Atilla Pethö; Michael Pohst (Hrsg.): Algebraische Algorithmen. Vieweg, 1999, ISBN 9783528065980, S. 183.
  • Michael Kaplan: Computeralgebra. Springer, 2005, ISBN 3540213791, S. 239.
  • Elwyn R. Berlekamp: Factoring Polynomials Over Finite Fields. Bell System Technical Journal, Band 46, 1967, Seiten 1853-1859 bzw. in: Elwyn R. Berlekamp: Algebraic Coding Theory. Mc-Graw Hill, 1968.

Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Berlekamp-Massey-Algorithmus — Der Berlekamp Massey Algorithmus (nach Elwyn Berlekamp und James Massey) dient dazu, das kürzeste, lineare rückgekoppelte Schieberegister zu finden, das eine gegebene Folge von Symbolen ausgibt. Die Symbole können aus einem beliebigen Körper… …   Deutsch Wikipedia

  • Elwyn Berlekamp — Elwyn Ralph Berlekamp (* 6. September 1940 in Dover (Ohio)) ist ein US amerikanischer Mathematiker und Informatiker, der sich insbesondere mit Kodierungstheorie und kombinatorischer Spieltheorie beschäftigt. Berlekamp in Banff 2005 Berlekamp… …   Deutsch Wikipedia

  • Linearfaktor — Als Faktorisierung von Polynomen in der Algebra versteht man analog zur Primfaktorzerlegung von ganzen Zahlen das Zerlegen von Polynomen in Faktoren. Inhaltsverzeichnis 1 Erklärung 2 Mathematische Beschreibung 3 Beispiele …   Deutsch Wikipedia

  • Linearfaktorzerlegung — Als Faktorisierung von Polynomen in der Algebra versteht man analog zur Primfaktorzerlegung von ganzen Zahlen das Zerlegen von Polynomen in Faktoren. Inhaltsverzeichnis 1 Erklärung 2 Mathematische Beschreibung 3 Beispiele …   Deutsch Wikipedia

  • Richard-W.-Hamming-Medaille — Die Richard W. Hamming Medaille ist eine Auszeichnung, die jährlich durch das IEEE (Institute of Electrical and Electronics Engineers) für außergewöhnliche Leistungen in der Informationstechnik vergeben wird. Die Medaille ist nach dem… …   Deutsch Wikipedia

  • Faktorisierung von Polynomen — Als Faktorisierung von Polynomen in der Algebra versteht man analog zur Primfaktorzerlegung von ganzen Zahlen das Zerlegen von Polynomen in Faktoren. Inhaltsverzeichnis 1 Erklärung 2 Mathematische Beschreibung 3 Beispiele …   Deutsch Wikipedia

  • Gold-Code — Ein linear rückgekoppeltes Schieberegister (engl. Linear Feedback Shift Register, kurz LFSR) ist ein rückgekoppeltes Schieberegister, welches zur Erzeugung von Pseudozufallszahlen eingesetzt werden kann. Inhaltsverzeichnis 1 Funktionsweise 2… …   Deutsch Wikipedia

  • Gold-Folge — Ein linear rückgekoppeltes Schieberegister (engl. Linear Feedback Shift Register, kurz LFSR) ist ein rückgekoppeltes Schieberegister, welches zur Erzeugung von Pseudozufallszahlen eingesetzt werden kann. Inhaltsverzeichnis 1 Funktionsweise 2… …   Deutsch Wikipedia

  • JPL-Folge — Ein linear rückgekoppeltes Schieberegister (engl. Linear Feedback Shift Register, kurz LFSR) ist ein rückgekoppeltes Schieberegister, welches zur Erzeugung von Pseudozufallszahlen eingesetzt werden kann. Inhaltsverzeichnis 1 Funktionsweise 2… …   Deutsch Wikipedia

  • James Lee Massey — (* 11. Februar 1934 in Wauseon, Ohio) ist ein Informationstheoretiker und Kryptologe. Er war Professor an der ETH Zürich. Seine bedeutendste Arbeiten waren die Entwicklung des Berlekamp Massey Algorithmus, der Entwurf des… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”