Direkt zum Inhalt

Lexikon der Mathematik: Berlekamp-Algorithmus

Algorithmus zur Faktorisierung von Polynomen mit ganzzahligen Koeffizienten. Der Algorithmus enthält folgende Schritte:

  1. Wir wählen eine Primzahl p, die nicht die Diskriminante des Polynoms f teilt.
  2. Wir faktorisieren das Polynom f über dem Primkörper 𝔽p der Chrakteristik p. Sei k die Zahl der Faktoren.
  3. Wenn k = 1 ist, ist das Polynom auch über ℤ irreduzibel und wir sind fertig.
  4. Wenn k > 1 ist, werden die Faktoren auf alle möglichen Weisen in zwei nicht-leere Teilmengen aufgeteilt. Wir wählen eine Partition und multiplizieren die Faktoren so, daß f modulo p zwei nichttriviale Faktoren g0 und h0 mit nicht verschwindender Resultante hat: \begin{eqnarray}f\equiv {g}_{o}{h}_{0}\,\mathrm{mod}\,p\end{eqnarray} und \begin{eqnarray}{\rm{Res}}({g}_{0},{h}_{0})\rlap{/}{\equiv }0\,\mathrm{mod}\,p.\end{eqnarray}
  5. Wir wenden das Henselsche Lemma an, um eine Zerlegung fgh mod pn zu erhalten, pn > B, die Koeffizienten von g und h werden zwischen −pn/2 und pn/2 gewählt. Wenn g das Polynom f über ℤ teilt, haben wir zwei nichttriviale Faktoren gefunden, auf die wir die Prozedur wieder anwenden können,
  6. Wenn g das Polynom f über ℤ nicht teilt und bereits alle anderen Partitionen getestet sind, ist f irreduzibel und wir sind fertig.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos