## [Algoritmo de Berlekamp](/es/node/63528) Definición Un algoritmo para factorizar polinomios sobre cuerpos finitos que usa álgebra lineal para encontrar la subálgebra de Berlekamp: se calcula una base de polinomios fijados por el mapa de Frobenius (x ↦ x^q) módulo el polinomio y se extraen factores no triviales mediante mcd con combinaciones lineales de elementos de la base. ## Principio Principio Aprovechar el endomorfismo de Frobenius x ↦ x^q sobre GF(q): el conjunto de clases residuales fijadas por Frobenius módulo un polinomio separable forma un espacio vectorial; resolver ecuaciones lineales para ese espacio reduce la factorización a álgebra lineal sobre el campo base seguida de separaciones por mcd. ## Demostración Demostración Dado un f sin factores múltiples en GF(p)[x], calcular la aplicación q-lineal inducida por a ↦ a^p en el anillo cociente y construir la matriz de (Frobenius − Identidad); su espacio nulo produce polinomios cuyos mcd con f dividen no trivialmente, produciendo factores irreducibles tras repeticiones. ## Aplicación incorrecta Aplicación incorrecta Aplicar el algoritmo sin eliminar primero factores repetidos (factorización sin factores múltiples) es incorrecto porque los cálculos del espacio fijo de Frobenius asumen separabilidad; considerar a Berlekamp práctico para q muy grandes sin mejoras modulares o aleatorias descuida la complejidad y la memoria necesarias. ## Consecuencia Consecuencia Berlekamp proporciona un método determinista y exacto de factorización sobre cuerpos finitos que es efectivo para tamaños de campo moderados; fue la primera metodología algebraica práctica para la factorización y sigue siendo fundamental en pasos deterministas de algoritmos híbridos. ## Inversión Inversión Contrastado con métodos de separación aleatorios (por ejemplo Cantor–Zassenhaus): en vez de usar álgebra lineal para hallar invariantes de forma determinista, la reversión emplea aleatoriedad para producir polinomios separadores probabilísticamente y con rapidez; ambos son marcos alternativos para el mismo fin. ## Límite Límite Diseñado para polinomios sobre cuerpos finitos y más eficaz en entradas sin factores múltiples y con tamaño de campo moderado; para campos muy grandes o grados extremadamente altos, los enfoques modulares aleatorios suelen ser preferibles en rendimiento. ## Tensión semántica Tensión semántica Tensión entre el enfoque determinista y de álgebra lineal de Berlekamp y los algoritmos aleatorizados: Berlekamp ofrece determinismo y estructura algebraica clara, mientras que los métodos aleatorizados tienden a ser más rápidos en la práctica pero carecen de garantía determinista. ## Síntesis Síntesis El algoritmo de Berlekamp reduce la factorización polinómica sobre cuerpos finitos a la resolución de ecuaciones lineales derivadas de la acción de Frobenius: al hallar las clases fijas de Frobenius y separar mediante mcd se obtiene una vía algebraica determinista para extraer factores.