El algoritmo de Berlekamp

En matemáticas , particularmente en álgebra computacional , el algoritmo de Berlekamp es un método bien conocido para factorizar polinomios sobre cuerpos finitos (también conocidos como cuerpos de Galois ). El algoritmo consiste principalmente en la reducción de matrices y el cálculo del máximo común divisor (MCD) de polinomios . Fue inventado por Elwyn Berlekamp en 1967. Fue el algoritmo dominante para resolver el problema hasta la aparición del algoritmo de Cantor-Zassenhaus en 1981. Actualmente se implementa en muchos sistemas de álgebra computacional conocidos .

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

Todos los posibles factores de${\displaystyle f(x)}$están contenidos dentro del anillo de factores

${\displaystyle R={\frac {\mathbb {F} _{q}[x]}{\langle f(x)\rangle }}.}$

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

${\displaystyle g(x)^{q}\equiv g(x){\pmod {f(x)}}.\,}$

Estos polinomios forman una subálgebra de R (que puede considerarse como una${\displaystyle n}$espacio vectorial de dimensión sobre${\displaystyle \mathbb {F} _{q}}$), llamada subálgebra de Berlekamp . La subálgebra de Berlekamp es de interés porque los polinomios${\displaystyle g(x)}$contiene satisfacción

${\displaystyle f(x)=\prod _{s\in \mathbb {F} _{q}}\gcd(f(x),g(x)-s).}$

En general, no todos los MCD del producto anterior serán un factor no trivial de${\displaystyle f(x)}$, pero algunos sí lo son, proporcionando los factores que buscamos.

El algoritmo de Berlekamp encuentra polinomios.${\displaystyle g(x)}$adecuado para su uso con el resultado anterior calculando una base para la subálgebra de Berlekamp. Esto se logra mediante la observación de que la subálgebra de Berlekamp es de hecho el núcleo de una determinada${\displaystyle n\times n}$matriz sobre${\displaystyle \mathbb {F} _{q}}$, que se deriva de la llamada matriz de Berlekamp del polinomio, denotada${\displaystyle {\mathcal {Q}}}$. Si${\displaystyle {\mathcal {Q}}=[q_{i,j}]}$entonces${\displaystyle q_{i,j}}$es el coeficiente de la${\displaystyle j}$término de potencia -ésima en la reducción de${\displaystyle x^{iq}}$módulo${\displaystyle f(x)}$, es decir:

${\displaystyle 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 cierto polinomio${\displaystyle g(x)\in R}$, decir:

${\displaystyle g(x)=g_{n-1}x^{n-1}+g_{n-2}x^{n-2}+\ldots +g_{0},\,}$

Podemos asociar el vector fila:

${\displaystyle g=(g_{0},g_{1},\ldots ,g_{n-1}).\,}$

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

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

Con algo de álgebra abstracta, la idea detrás del algoritmo de Berlekamp se vuelve conceptualmente clara. Representamos un campo finito.${\textstyle \mathbb {F} _{q}}$, dónde${\textstyle q=p^{m}}$para algunos principiante${\textstyle p}$, como${\textstyle \mathbb {F} _{p}[y]/(g(y))}$Podemos suponer que${\textstyle f(x)\in \mathbb {F} _ {q}[x]}$es libre de cuadrados, tomando todas las posibles raíces p-ésimas y luego calculando el mcd con su derivada.

Ahora, supongamos que${\textstyle f(x)=f_{1}(x)\ldots f_{n}(x)}$es la factorización en irreducibles. Entonces tenemos un isomorfismo de anillos,${\textstyle \sigma$ :\mathbb {F} _{q}[x]/(f(x))\to \prod _{i}\mathbb {F} _{q}[x]/(f_{i}(x))} , dado por el teorema chino del resto . La observación crucial es que el automorfismo de Frobenius${\textstyle x\to x^{p}}$se desplaza con${\textstyle \sigma }$, de modo que si denotamos${\textstyle {\text{Fix}}_{p}(R)=\{f\in R:f^{p}=f\}}$, entonces${\textstyle \sigma }$se restringe a un isomorfismo${\textstyle {\text{Fix}}_{p}(\mathbb {F} _{q}[x]/(f(x)))\to \prod _{i=1}^{n}{\text{Fix}}_{p}(\mathbb {F} _{q}[x]/(f_{i}(x)))}$. Por teoría de campos finitos, ${\textstyle {\text{Fix}}_{p}(\mathbb {F} _{q}[x]/(f_{i}(x)))}$es siempre el subcampo principal de esa extensión de campo. Por lo tanto,${\textstyle {\text{Fix}}_{p}(\mathbb {F} _{q}[x]/(f(x)))}$tiene ${\textstyle p}$elementos si y solo si ${\textstyle f(x)}$es irreductible.

Además, podemos usar el hecho de que el automorfismo de Frobenius es${\textstyle \mathbb {F} _{p}}$-lineal para calcular el conjunto fijo. Es decir, observamos que${\textstyle {\text{Fix}}_{p}(\mathbb {F} _{q}[x]/(f(x)))}$es un${\textstyle \mathbb {F} _{p}}$-subespacio, y se puede calcular una base explícita para él en el anillo polinomial${\textstyle \mathbb {F} _ {p}[x,y]/(f,g)}$mediante computación${\textstyle (x^{i}y^{j})^{p}}$y estableciendo las ecuaciones lineales sobre los coeficientes de${\textstyle x,y}$polinomios que se satisfacen si y solo si Frobenius los fija. Observamos que en este punto tenemos un criterio de irreducibilidad computable eficientemente, y el análisis restante muestra cómo usarlo para encontrar factores.

El algoritmo ahora se divide en dos casos:

• En el caso de pequeños ${\textstyle p}$podemos construir cualquier ${\textstyle g\in {\text{Fix}}_{p}(\mathbb {F} _{q}[x]/(f(x)))\setminus \mathbb {F} _{p}}$y luego observamos que para algunos${\textstyle a\in \mathbb {F} _ {p}}$hay${\textstyle i,j}$de modo que${\textstyle ga=0\mod f_{i}}$y${\textstyle ga\not =0\mod f_{j}}$. Tal es${\textstyle ga}$tiene un factor no trivial en común con${\textstyle f(x)}$, que se puede calcular mediante el mcd. Como${\textstyle p}$es pequeño, podemos recorrer todas las posibilidades${\textstyle a}$.
• Para el caso de primos grandes, que son necesariamente impares, se puede aprovechar el hecho de que un elemento aleatorio distinto de cero de${\textstyle \mathbb {F} _ {p}^{*}}$es un cuadrado con probabilidad${\textstyle 1/2}$y que el mapa${\textstyle x\to x^{\frac {p-1}{2}}}$mapea el conjunto de cuadrados no nulos a${\textstyle 1}$y el conjunto de no cuadrados para${\textstyle -1}$Por lo tanto, si tomamos un elemento aleatorio${\textstyle g\in {\text{Fix}}_{p}(\mathbb {F} _{q}[x]/f(x))}$, entonces con buena probabilidad${\estilo de texto g^{\frac {p-1}{2}}-1}$tendrá un factor no trivial en común con${\textstyle f(x)}$.

Para obtener más detalles, puede consultar ^{[ 1 ] .}

Una aplicación importante del algoritmo de Berlekamp es el cálculo de logaritmos discretos sobre campos finitos.${\displaystyle \mathbb {F} _{p^{n}}}$, dónde${\displaystyle p}$es primordial y${\displaystyle 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 los elementos del campo. Si representamos el campo${\displaystyle \mathbb {F} _{p^{n}}}$de la forma habitual, es decir, como polinomios sobre el campo base.${\displaystyle \mathbb {F} _{p}}$, reducido módulo un polinomio irreducible de grado${\displaystyle n}$- entonces se trata simplemente de una factorización polinómica, tal como la proporciona el algoritmo de Berlekamp.

Se puede acceder al algoritmo de Berlekamp en el paquete PARI/GP usando el comando factormod y WolframAlpha.sitio web.

• Factorización de polinomios
• Factorización de polinomios sobre un cuerpo finito y pruebas de irreducibilidad
• Algoritmo de Cantor-Zassenhaus

• 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 Posteriormente republicado en: Berlekamp, ​​Elwyn R. (1968). Teoría de la codificación algebraica . McGraw Hill. ISBN 0-89412-063-8.
• Knuth, Donald E. (1997). «4.6.2 Factorización de polinomios». Algoritmos seminuméricos . El arte de la programación informática . Vol.  2 (Tercera  ed.). Reading, Massachusetts: Addison-Wesley. pp. 439–461 , 678–691 . ISBN  0-201-89684-2.