Algoritmo de Berlekamp - Enciclopedia

En matemáticas, especialmente en álgebra computacional, el algoritmo de Berlekamp es un método conocido para factorizar polinomios sobre campos finitos (también conocidos como campos de Galois). El algoritmo consta principalmente de reducción de matrices y cálculos de CGM (máximo común múltiplo de polinomios). Fue inventado por Elwyn Berlekamp en 1967. Fue el algoritmo dominante para resolver el problema hasta que se introdujo el algoritmo Cantor–Zassenhaus en 1981. Actualmente está implementado en muchos sistemas de álgebra computacional conocidos.

Resumen
El algoritmo de Berlekamp toma como entrada un polinomio de grado \( n \) con coeficientes en un campo finito \( \mathbb{F}_q \) (es decir, uno sin factores repetidos) y da como salida un polinomio \( g(x) \) con coeficientes en el mismo campo tal que \( g(x) \) divide \( f(x) \). Luego, el algoritmo puede aplicarse recursivamente a estos y a los siguientes divisores, hasta encontrar la descomposición de \( f(x) \) en potencias de polinomios irreducibles (recordando que el anillo de polinomios sobre un campo finito es un dominio de factorización única). Todos los posibles factores de \( f(x) \) están contenidos dentro del anillo de factores

\[ R = \frac{\mathbb{F}_q[x]}{\langle f(x) \rangle}. \]

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

\[ g(x)^q \equiv g(x) \pmod{f(x)}. \]

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

\[ f(x) = \prod_{s \in \mathbb{F}_q} \gcd(f(x), g(x) - s). \]

En general, no todos los CGM en el producto anterior serán factores no triviales de \( f(x) \), pero algunos lo son, proporcionando los factores que buscamos. El algoritmo de Berlekamp encuentra polinomios \( g(x) \) adecuados para usar con el resultado anterior al calcular una base para el subálgebra de Berlekamp. Esto se logra mediante la observación de que el subálgebra de Berlekamp es, de hecho, el núcleo de una cierta matriz \( n \times n \) sobre \( \mathbb{F}_q \), que se deriva de la llamada matriz de Berlekamp del polinomio, denotada \( \mathcal{Q} \). Si \( \mathcal{Q} = [q_{i,j}] \) entonces \( q_{i,j} \) es el coeficiente del término de potencia \( j \)-ésimo en la reducción de \( x^{iq} \) módulo \( f(x) \), es decir:

\[ x^{iq} \equiv q_{i,n-1}x^{n-1} + q_{i,n-2}x^{n-2} + \ldots + q_{i,0} \pmod{f(x)}. \]

Con un polinomio \( g(x) \in R \), digamos:

\[ g(x) = g_{n-1}x^{n-1} + g_{n-2}x^{n-2} + \ldots + g_0, \]

podemos asociar el vector fila:

\[ g = (g_0, g_1, \ldots, g_{n-1}). \]

Es relativamente sencillo ver que el vector fila \( g\mathcal{Q} \) corresponde, de la misma manera, a la reducción de \( g(x)^q \) módulo \( f(x) \). Consecuentemente, un polinomio \( g(x) \in R \) está en el subálgebra de Berlekamp si y solo si \( g(\mathcal{Q} - I) = 0 \) (donde \( I \) es la matriz identidad \( n \times n \)), es decir, si y solo si está en el espacio nulo de \( \mathcal{Q} - I \).

Al calcular la matriz \( \mathcal{Q} - I \) y reducirla a la forma escalonada reducida y luego fácilmente leer una base para el espacio nulo, podemos encontrar una base para el subálgebra de Berlekamp y, por lo tanto, construir polinomios \( g(x) \) en él. Luego necesitamos calcular sucesivamente CGM de la forma anterior hasta encontrar un factor no trivial. Dado que el anillo de polinomios sobre un campo es un dominio euclidiano, podemos calcular estos CGM utilizando el algoritmo euclidiano.

Explicación algebraica conceptual
Con algunas ideas de álgebra abstracta, la idea detrás del algoritmo de Berlekamp se vuelve conceptualmente clara. Representamos un campo finito \( \mathbb{F}_q \), donde \( q = p^m \) para algún número primo \( p \), como \( \mathbb{F}_p[y]/(g(y)) \). Podemos suponer que \( f(x) \in \mathbb{F}_q[x] \) es cuadrático, tomando todas las posibles raíces \( p \)-tas y luego calculando el CGM con su derivada.

Ahora, supongamos que \( f(x) = f_1(x) \ldots f_n(x) \) es la factorización en irreducibles. Entonces tenemos una isomorfismo de anillos, \( \sigma: \mathbb{F}_q[x]/(f(x)) \to \prod_i \mathbb{F}_q[x]/(f_i(x)) \), dado por el teorema chino restituyente. La observación crucial es que el automorfismo de Frobenius \( x \to x^p \) conmuta con \( \sigma \), por lo que si denotamos \( {\text{Fix}}_p(R) = \{f \in R : f^p = f\} \), entonces \( \sigma \) se restringe a un isomorfismo \( {\text{Fix}}_p(\mathbb{F}_q[x]/(f(x))) \to \prod_i {\text{Fix}}_p(\mathbb{F}_q[x]/(f_i(x))) \). Por teoría de campos finitos, \( {\text{Fix}}_p(\mathbb{F}_q[x]/(f_i(x))) \) siempre es el subcampo primo de esa extensión de campo. Por lo tanto, \( {\text{Fix}}_p(\mathbb{F}_q[x]/(f(x))) \) tiene \( p \) elementos si y solo si \( f(x) \) es irreducible.

Además, podemos usar el hecho de que el automorfismo de Frobenius es lineal en \( \mathbb{F}_p \) para calcular el conjunto fijo. Es decir, notamos que \( {\text{Fix}}_p(\mathbb{F}_q[x]/(f(x))) \) es un subespacio \( \mathbb{F}_p \), y una base explícita para él puede calcularse en el anillo de polinomios \( \mathbb{F}_p[x,y]/(f,g) \) calculando \( (x^i y^j)^p \) y estableciendo las ecuaciones lineales sobre los coeficientes de los polinomios \( x, y \) que se satisfacen si y solo si está fijo por Frobenius. Notamos que en este punto tenemos un criterio de irreducibilidad eficiente, y el resto del análisis muestra cómo usarlo para encontrar factores.

El algoritmo ahora se descompone en dos casos:

En el caso de números primos pequeños \( p \), podemos construir cualquier \( g \in {\text{Fix}}_p(\mathbb{F}_q[x]/(f(x))) \setminus \mathbb{F}_p \), y luego observar que para algún \( a \in \mathbb{F}_p \) hay \( i, j \) tales que \( g - a = 0 \mod f_i \) y \( g - a \neq 0 \mod f_j \). Tal \( g - a \) tiene un factor no trivial en común con \( f(x) \), que se puede calcular mediante el CGM. Como \( p \) es pequeño, podemos recorrer todos los posibles \( a \).

Para el caso de números primos grandes, que necesariamente son impares, se puede aprovechar el hecho de que un elemento aleatorio no nulo de \( \mathbb{F}_p^* \) es un cuadrado con probabilidad \( \frac{1}{2} \), y que el mapa \( x \to x^{\frac{p-1}{2}} \) mapea el conjunto de cuadrados no nulos al 1 y el conjunto de no cuadrados al -1. Por lo tanto, si tomamos un elemento aleatorio \( g \in {\text{Fix}}_p(\mathbb{F}_q[x]/f(x)) \), con buena probabilidad \( g^{\frac{p-1}{2}} - 1 \) tendrá un factor no trivial en común con \( f(x) \).

Para obtener más detalles, se puede consultar.

Aplicaciones
Una aplicación importante del algoritmo de Berlekamp es en el cálculo de logaritmos discretos sobre campos finitos \( \mathbb{F}_{p^n} \), donde \( p \) es primo y \( n \geq 2 \). El cálculo de logaritmos discretos es un problema importante en la criptografía de clave pública y la codificación de control de errores. Para un campo finito, el método más rápido conocido es el método del cálculo de índices, que implica la factorización de elementos del campo. Si representamos el campo \( \mathbb{F}_{p^n} \) de la manera usual, es decir, como polinomios sobre el campo base \( \mathbb{F}_p \), reducidos módulo un polinomio irreducible de grado \( n \), esto es simplemente factorización de polinomios, como proporciona el algoritmo de Berlekamp.

Implementación en sistemas de álgebra computacional
El algoritmo de Berlekamp puede accederse en el paquete PARI/GP utilizando el comando factormod y en el sitio web WolframAlpha [1].

Véase también
Factorización de polinomios
Factorización de polinomios sobre un campo finito y pruebas de irreducibilidad
Algoritmo Cantor–Zassenhaus

Referencias
Berlekamp, Elwyn R. (1967). "Factoring Polynomials Over Finite Fields". Bell System Technical Journal. 46 (8): 1853–1859. doi:10.1002/j.1538-7305.1967.tb03174.x. MR 0219231. BSTJ Más tarde reimpreso en: Berlekamp, Elwyn R. (1968). Algebraic Coding Theory. McGraw Hill. ISBN 0-89412-063-8.
Knuth, Donald E (1997). "4.6.2 Factorization of Polynomials". Seminumerical Algorithms. The Art of Computer Programming. Vol. 2 (Tercera ed.). Reading, Massachusetts: Addison-Wesley. pp. 439–461, 678–691. ISBN 0-201-89684-2.