El algoritmo de Berlekamp

---

En matemáticas , particularmente álgebra computacional , el algoritmo de Berlekamp es un método bien conocido para factorizar polinomios sobre campos finitos (también conocidos como campos de Galois ). El algoritmo consiste principalmente en cálculos de reducción de matrices y polinomios GCD . Fue inventado por Elwyn Berlekamp en 1967. Fue el algoritmo dominante para resolver el problema hasta el algoritmo Cantor-Zassenhaus de 1981. Actualmente está implementado en muchos sistemas de álgebra computacional conocidos .

El algoritmo de Berlekamp toma como entrada un polinomio libre de cuadrados (es decir, uno sin factores repetidos) de grado con coeficientes en un campo finito y da como salida un polinomio con coeficientes en el mismo campo tal que divide . Luego, el algoritmo se puede aplicar de forma recursiva a estos divisores y a los siguientes, hasta que encontremos la descomposición de en potencias de polinomios irreducibles (recordando que el anillo de polinomios sobre un campo finito es un dominio de factorización único ).${\ Displaystyle f (x)}$${\ Displaystyle n}$${\displaystyle \mathbb {F} _{q}}$${\displaystyle g(x)}$${\displaystyle g(x)}$${\displaystyle f(x)}$${\displaystyle f(x)}$

Todos los factores posibles de están contenidos en el anillo de factores.${\displaystyle f(x)}$

El algoritmo se centra en polinomios que satisfacen la congruencia:${\displaystyle g(x)\in R}$

Estos polinomios forman una subálgebra de R (que se puede considerar como un espacio vectorial -dimensional ), llamada subálgebra de Berlekamp . La subálgebra de Berlekamp es de interés porque los polinomios que contiene satisfacen${\displaystyle n}$${\displaystyle \mathbb {F} _{q}}$${\displaystyle g(x)}$

En general, no todos los GCD en el producto anterior serán un factor no trivial de , pero algunos lo son, que brinden los factores que buscamos.${\displaystyle f(x)}$

---