Berlekamp-Algorithmus

Ein Algorithmus zur Faktorisierung von Polynomen über endlichen Körpern, der Lineare Algebra nutzt, um die Berlekamp-Unteralgebra zu finden: Man berechnet eine Basis von Polynomen, die durch die Frobenius-Abbildung (x ↦ x^q) modulo des Polynoms fixiert sind, und extrahiert nichttriviale Faktoren mittels ggT mit linearen Kombinationen der Basisvektoren.