Algoritmo de Berlekamp

El algoritmo de Berlekamp es un algoritmo diseñado para factorizar polinomios unitarios sobre un campo finito . Diseñado por Alvin Berlekamp en 1967 . También se puede utilizar para probar la irreductibilidad de polinomios sobre campos finitos . La idea principal del algoritmo es la posibilidad de representar el polinomio original como un producto de los máximos comunes divisores del propio polinomio y algunos polinomios que se expanden hasta un término libre. $F$

El algoritmo de Berlekamp tiene una alta complejidad computacional, por lo que se han desarrollado varios métodos adicionales para reducir el número de operaciones matemáticas necesarias. Sin embargo, a pesar de su complejidad, el algoritmo de Berlekamp se ha implementado en sistemas de álgebra computacional. El algoritmo ha encontrado una amplia aplicación en la teoría de la codificación y en el estudio de las relaciones de recurrencia lineal en campos finitos. Hay muchos problemas computacionales en álgebra y teoría de números que de alguna manera están relacionados con la descomposición de polinomios en campos finitos, por ejemplo, factorizar polinomios en el anillo de números enteros , encontrar la descomposición de un número racional primo en el campo de números algebraicos, calcular el grupo de Galois de alguna ecuación sobre el campo de los números racionales y la construcción de extensiones de campo.

Historial de creación

Un matemático estadounidense, profesor de la Universidad de California, Berlekamp, estudió los códigos de detección y corrección de errores cíclicos , incluido el código Bose-Chowdhury-Hockwingham , cuyas propiedades dependen de los divisores de los polinomios generadores. Los avances técnicos de Berlekamp en la decodificación de estos códigos los han hecho más prácticos [1] .

El algoritmo se describió por primera vez en el artículo "Factorización de polinomios sobre campos finitos" [2] y luego se reprodujo en el libro "Teoría de la codificación algebraica" [2] . En este artículo de 1967 [3], Berlekamp escribe que el problema de la factorización surge en los escritos de Golomb [4] . Sin embargo, la posibilidad de utilizar una matriz para determinar el número de factores normalizados de un polinomio se notó por primera vez en un artículo de Karel Piotr. $B$ $f(x)$ [5] . El artículo de Butler [6] encontró que el rango de una matrizes, otra prueba de este hecho la dio Schwartz [7] . $SER$ $nk$

El algoritmo de Berlekamp fue mencionado en muchos trabajos [8] y fue el principal algoritmo para resolver el problema de factorización hasta la llegada del algoritmo de Cantor-Zassenhaus en 1981.[9] . Se desarrolló una técnica [10] que permite factorizar un polinomio endonde es un indicador en la estimación de la complejidad de multiplicar matrices cuadradas [11] . $O(n^{{(\omega +1)/2+o(1)}}+n^{{1+o(1)}}\log q),$ $\omega$

Declaración y definiciones

Se plantea el problema de la factorización de un polinomio de grado ( ) sobre un cuerpo finito ( , es un número primo ) [12] en varios polinomios unitarios irreducibles . $f(x)$ $norte$ $n\geq 2$ $\mathbb {F} _{q}$ $q=p^{m}$ $pags$ $f(x)=f_{1}(x)^{{e_{1}}}\cdots f_{k}(x)^{{e_{k}}}$

Para su uso en el algoritmo, se construye una matriz de acuerdo con las siguientes condiciones: $B=(b_{{ij}})_{{i=0,\;j=0}}^{{n-1,\;n-1}}$

{x^{iq}}\equiv \sum _{j=0}^{n-1}b_{ij}x^{j}{\pmod {f(x)))\quad i={ \sobrelínea {0,n-1}}

Un polinomio tal que , se llama polinomio en descomposición [13] . $h(x)\in \mathbb {F} _{q}[x]$ $1\leqslant \deg {h(x)}<n,\quad {h(x)}^{q}\equiv h(x){\pmod {f(x)}}$ $F$

Caso básico

Algoritmo de factorización sobre un campo finito de un polinomio de la forma: $\mathbb {F} _{q}$

f(x)=f_{1}(x)\cdots f_{k}(x)

consta de los siguientes pasos:

Cálculo matricial [14] . $B$
Buscar la base del subespacio de soluciones del sistema de ecuaciones lineales [15] : $\overline {e_{1}},\puntos,\overline {e_{k}}$ $(B-E_{n})^{T}\mathbf {x} =\mathbf {0}$ , en este caso, es posible elegir el vector , ya que siempre estará presente [15] en la base del espacio solución debido a que en . $\overline {e_{1}}=(1,\;0,\;....\;,\;0)$ $x^{iq}\equiv 1{\pmod {f(x)))$ $yo=0$
El número encontrado es el número de divisores irreducibles [14] . $k$ $f(x)$
- Si , entonces el polinomio es
irreducible . $k=1$
Si , entonces los vectores tienen la forma . Estos números se utilizan para construir polinomios en descomposición: $k>1$ $\sobrelínea {e_{l}}$ $(h_{{l,\;0}},\puntos,h_{{l,\;n-1}})$ $F$ $h_{l}(x)=\sum _{i=0}^{n-1}h_{l,\;i}\;x^{i},\quad l={\overline {2 ,\;k}},\quad h_{1}(x)=1.$ .
Búsqueda de descomposición [15] : $f(x)=\prod_{{c\in {\mathbb {F}}_{q},}}\gcd(f(x),h_{2}(x)-c)$ como: $f(x)=\prod _{m}g_{{m,\;2}}(x)$ , donde , en el caso general, no son irreducibles. Las funciones se factorizan de la misma manera [15] , es decir: $g_{{m,\;s}}(x),\quad s=\overline {2,k}$ $g_{{m,\;s}}(x)$ $g_{{m,\;s}}(x)=\prod_{{c\in {\mathbb {F}}_{q},}}\gcd(g_{{m,\;s}}( x),h_{{s+1}}(x)-c),\quad s=\overline {2,k-1}$ .

Caso general

El problema de la factorización de un polinomio unitario arbitrario se reduce a la consideración del caso principal. Para ello se calcula el polinomio

d(x)=\gcd(f(x),\;f^{{'}}(x))

utilizando el algoritmo de Euclides .

Si entonces el polinomio no contiene raíces múltiples, ya que la raíz múltiple es también la raíz de la derivada [16] . $d(x)=1,$
Si entonces significa Si entonces para ello es necesario hacer el procedimiento descrito hasta obtener el desarrollo El polinomio satisface los requisitos del caso principal [16] . $d(x)=f(x),$ $f^{{'}}(x)=0,$ $f(x)=g(x)^{p},\quad g(x)\in \mathbb {F}_{q}[x].$ $g^{{'}}(x)=0,$ $g(x)$ $f(x)=h(x)^{{p^{s}}},h{'}(x)\neq 0.$ $h(x)$
De lo contrario, el polinomio es un divisor no trivial del polinomio . A su vez, el polinomio no tiene factores múltiples irreducibles [16] . Si contiene múltiples factores, entonces también se le aplica el procedimiento descrito. Conociendo estas expansiones, es fácil obtener la expansión . $d(x)$ $f(x)$ ${\frac{f(x)}{d(x)))$ $d(x)$ $f(x)$

Así, el problema de factorizar un polinomio unitario arbitrario sobre un cuerpo finito se reduce a factorizar un número finito de polinomios que no tienen múltiples factores irreducibles, es decir, al caso principal [16] . ${\ estilo de visualización \ mathbb {F} _ {q} [x]}$

Justificación

Dejar:

f(x)=f_{1}(x)^{{e_{1}}}\cdots f_{k}(x)^{{e_{k}}}

, donde .

\quad e_{i}=1,\quad i=\overline {1,k}

De acuerdo con el teorema chino del resto, existe un polinomio único para cualquier conjunto de elementos de campo [17] : $(c_{1},\;...,\;c_{k})$ $\mathbb {F} _{q}$

h(x)\in {\mathbb {F}}_{q}[x],

tal que:

h(x)\equiv c_{i}{\pmod {f_{i}(x))),\;i=\overline {1,\;k},\quad \deg {h(x)}<\ grado{f(x)}

El polinomio satisface la condición [17] : $h(x)$

{h(x)}\equiv c_{i}\equiv c_{i}^{q}\equiv h(x)^{q}{\pmod {f_{i}(x)))),\quad i = \sobrelínea {1,\;k}

y así [18] :

{\displaystyle h(x)^{q}\equiv h(x){\pmod {f(x)))),\quad \deg {h(x)}<deg{f(x))))

De la condición:

h(x)^{q}-h(x)=\prod_{{c\in {\mathbb {F}}_{q}}}(h(x)-c)\equiv 0{\pmod { f(x)}}

y del hecho de que los factores del lado derecho son coprimos se sigue que cada divisor irreducible del polinomio divide a uno y sólo a uno de los polinomios . Así, se prueba la validez y unicidad de la descomposición [18] : $f(x)$ $h(x)-c$

f(x)=\prod_{{c\in {\mathbb {F}}_{q}}}\gcd(f(x),h(x)-c).

Para encontrar un polinomio:

h(x)=a_{0}+a_{1}x^{1}+\puntos +a_{{n-1}}x^{{n-1}}\in {\mathbb {F}}_ {q}

Veamos la comparación:

h(x)^{q}\equiv h(x){\pmod {f(x)))

que es equivalente a la condición [17] :

\sum_{{i=0}}^{{n-1}}a_{i}x^{{iq}}\equiv \sum_{{i=0}}^{{n-1}}a_ {i}x^{i}{\pmod {f(x)))

Por la definición de la matriz, obtenemos: $B$

\sum_{{i=0}}^{{n-1}}a_{i}\sum_{{j=0}}^{{n-1}}b_{{ij}}x^{j }=\sum_{{i=0}}^{{n-1}}a_{i}x^{i}

entonces [17] :

\sum _{i=0}^{n-1}a_{i}b_{ij}=a_{j},\quad j={\overline {0,\;n-1))

El sistema de ecuaciones resultante determina los coeficientes de los polinomios en descomposición y se puede escribir como: $F$

\quad (a_{0},\;a_{1},...,a_{{n-1}})B=(a_{0},\;a_{1},\;...,a_ {{n-1}})

\quad (a_{0},\;a_{1},...,a_{n-1})(B-E_{n})=\mathbf {0}

[17] .

Complejidad del algoritmo

La complejidad del algoritmo son las operaciones matemáticas [19] . El algoritmo será efectivo solo para campos pequeños. Esto se debe a la necesidad de enumerar todos . $O(n^{3}+qkn)$ ${\displaystyle c\in \mathbb {F} _{q))$

Mejoras

En el caso de un campo simple, si el valor es grande, la iteración de los valores llevará mucho tiempo. Sin embargo, es posible definir un conjunto que consiste en que no es trivial [20] . Para ello, es necesario encontrar las raíces de la resultante [21] , que conformarán el conjunto . $pags$ $c\in {\mathbb {Z} /p\mathbb {Z} }$ $METRO$ $C$ $\gcd(f(x),h(x)-c)$ $R(c)$ $METRO$
Otro método de descomposición de un polinomio unitario , que no tiene múltiples factores irreducibles, se basa en reducir alguna matriz A que sea efectivamente computable utilizando el algoritmo de Berlekamp a una forma diagonal [22] . Sin embargo, el proceso de diagonalización en sí mismo es bastante complicado. $f(x)\in GF(q)[x]$
Kaltofen y Lobo [23] propusieron una versión probabilística del algoritmo de Berlekamp, que permite factorizar un polinomio de grado en operaciones aritméticas. El algoritmo de Kaltofen-Lobo se implementó en una computadora y resultó ser eficiente para polinomios de alto grado, por ejemplo, para polinomios de grado 10001 , funciona en un campo durante aproximadamente 102,5 horas en una computadora Sun-4 . $f(x)\in GF(q)[x]$ $norte$ $O((n\log n+\log q)\cdot n(\log n)\log(\log n))$ ${\ estilo de visualización \ mathbb {Z} /127 \ mathbb {Z}}$

Aplicación

Los algoritmos de factorización de polinomios son importantes para la teoría de la codificación y para el estudio de las relaciones de recurrencia lineal en campos finitos. Además, el algoritmo de Berlekamp se usa para calcular el grupo de Galois de una ecuación sobre el campo de los números racionales y construir soluciones de campo, expandir polinomios sobre el anillo de los enteros, para encontrar la descomposición de un número racional simple en el campo de los números algebraicos, y para algunos otros problemas computacionales [24] . Algoritmos con bases factorialesutilizar algoritmos de factorización de polinomios para resolver el problema de encontrar un logaritmo discreto [25] , sobre cuya complejidad computacional se construye el esquema de ElGamal .

Implementaciones en sistemas de álgebra computacional

En el sistema de álgebra computacional PARI/GP , el algoritmo de Berlekamp se puede utilizar con el comando factormod[26] .

Notas

↑ Berlekamp, 1967 , pág. 1854: "Sobre los códigos cíclicos".
↑ 1 2 Berlekamp, 1967 .
↑ Berlekamp, 1967 , pág. 1853.
↑ Golomb, Solomon Wolf. Secuencias de registro de desplazamiento . — Parque Egeo Pr; Edición revisada, 1981. - 274 p. — ISBN 978-0894120480 .
↑ PETR K. Uber die Reduzibilitat eines Polynoms mit ganzzahligen Koeffi-zienten nach einem Primzahlmodul. - Estera de plagas Casopis. Fys, 1937, págs. 85-94 .
↑ Butler, MCR Sobre la reducibilidad de polinomios sobre un campo finito. - The Quarterly Journal of Mathematics Oxford Second Series 5, 1954. - S. 102-107 .
↑ Schwarz, St. Sobre la reducibilidad de polinomios sobre un campo finito. — Cuarto. Matemáticas J. Oxford Ser. (2) 7, 1956. - págs. 110-124 .
↑ Lidl, 1988 , Comentario histórico, p. 223-224.
↑ Cantor DG, Zassenhaus H. Un nuevo algoritmo para factorizar polinomios sobre campos finitos. - Matemáticas. Comp., 1981. vol. 36. - Pág. 587-592.
↑ von zur Gathen J., Shoup V. Cálculo de mapas de Frobenius y factorización de polinomios. - Computadora. Complejidad, 1992. - Vol. 2 . - S. 187-224 .
↑ Vasilenko, 2003 , pág. 185: "La complejidad del algoritmo de Cantor-Zassenhaus".
↑ Lidl, 1988 , Planteamiento del problema, p. 187.
↑ Vasilenko, 2003 , Definiciones, p. 172.
↑ 1 2 Vasilenko, 2003 , Descripción del algoritmo, p. 173.
↑ 1 2 3 4 Lidl, 1988 , Descripción del algoritmo.
↑ 1 2 3 4 Lidl, 1988 , Reducción al caso principal, p. 188.
↑ 1 2 3 4 5 Lidl, 1988 , Justificación de la corrección del algoritmo, p. 189-190.
↑ 1 2 Vasilenko, 2003 , pág. 174.
↑ Vasilenko, 2003 , pág. 174: "La complejidad del algoritmo".
↑ Lidl, 1988 , Más sobre el método, p. 201.
↑ Van der Waerden, 1976 , Sobre la resultante, p. 124.
↑ Lidl, 1988 , Más sobre el método, p. 206.
↑ Kaltofen E, Lobo A. Factorización de polinomios de alto grado mediante el algoritmo Berlekamp de caja negra // Actas del simposio internacional sobre computación simbólica y algebraica (ISSAC '94). - N. Y. : ACM Press, 1994. - P. 90-98 . — ISBN 0-89791-638-7 . -doi : 10.1145/ 190347.190371 .
↑ Lidl, 1988 , Aplicación del algoritmo, p. 187.
↑ Vasilenko, 2003 , Sobre el uso de algoritmos con bases factoriales para resolver el problema del logaritmo discreto, p. 137.
↑ Catálogo de funciones GP/PARI: Funciones aritméticas Archivado el 11 de marzo de 2007.

Literatura

Berlekamp, Elwyn R. Factorización de polinomios sobre campos finitos // Bell System Technical Journal. - 1967. - vol. 46 . - Pág. 1853-1859 . BSTJ Posteriormente republicado en: Berlekamp, Elwyn R. Teoría de codificación algebraica . - Educación de McGraw-Hill , 1968. - ISBN 0-89412-063-8 .
Vasilenko O. N. Algoritmos teóricos de números en criptografía . - M. : MTSNMO, 2003. - 328 p. — ISBN 5-94057-103-4 .
Lidl R. , Niederreiter G. Campos finitos = Campos finitos / Ed. V. I. Nechaev. - 1ª ed. - M. : Mir, 1988. - T. 1. - 430 p. — ISBN 5-03-000065-8 .
Van der Waerden B. L. álgebra _ — M.: Nauka, 1976. — 646 p. Archivadoel 2 de noviembre de 2013 enWayback Machine