Algoritmo de Berlekamp-Rabin

El algoritmo de Berlekamp-Rabin (también el método de Berlekamp ) es un método probabilístico para encontrar las raíces de polinomios sobre un campo con complejidad polinomial . El método fue descrito por el matemático estadounidense Alvin Berlekamp en 1970 [1] como un derivado del algoritmo de factorización para polinomios sobre campos finitos y más tarde (en 1979) fue modificado por Michael Rabin para el caso de campos finitos arbitrarios [2] . La versión original del algoritmo propuesto por Berlekamp en 1967 [3] no era polinomial [4] . La versión del algoritmo publicada en 1970 basada en los resultados de Zassenhaus trabajaba con valores grandes de , en la que se usaba el método del título como auxiliar [1] . En el momento de la publicación, el método era común en el entorno profesional, pero rara vez se encontraba en la literatura [4] . $\mathbb {F} _{p}$ $pags$

Historia

El método fue propuesto por Alvin Berlekamp en su trabajo sobre la factorización de polinomios sobre campos finitos [1] . En él, la factorización de un polinomio en factores irreducibles sobre un cuerpo se reduce a encontrar las raíces de algunos otros polinomios sobre un cuerpo . Al mismo tiempo, en el trabajo original no había pruebas de la corrección del algoritmo [2] . El algoritmo fue finalizado y generalizado para el caso de campos finitos arbitrarios por Michael Rabin [2] . En 1986, René Peralta describió un algoritmo similar [5] que resuelve el problema de encontrar la raíz cuadrada en un campo [6] , y en 2000 se generalizó el método de Peralta para resolver ecuaciones cúbicas [7] . ${\mathbb F}_{{p^{k))}$ $\mathbb {F} _{p}$ $\mathbb {F} _{p}$

En el algoritmo de Berlekamp , un polinomio se representa primero como un producto , donde es el producto de polinomios de grado . Luego, la factorización de cada polinomio de grado se reduce a encontrar las raíces del nuevo polinomio de grado . El artículo que presenta el algoritmo de factorización también proponía tres métodos para encontrar las raíces de un polinomio en un campo de Galois . Los dos primeros reducen encontrar raíces en un campo a encontrar raíces en un campo . El tercer método, que es el tema de este artículo, resuelve el problema de encontrar raíces en el campo , que, junto con los otros dos, resuelve el problema de factorización [1] . ${\displaystyle f(x)=a_{0}+a_{1}x+\dots +a_{n}x^{n))$ $f(x)=h_{1}(x)h_{2}(x)\puntos h_{n}(x)$ $hola}$ $Rhode Island}$ $i$ $h_{i}(x)$ $ir_{yo}$ $H(x)$ $Rhode Island}$ ${\mathbb F}_{{p^{k))}$ ${\mathbb F}_{{p^{k))}$ $\mathbb {F} _{p}$ $\mathbb {F} _{p}$

La versión del algoritmo de factorización propuesto por Berlekamp en su primer artículo en 1967 [3] corrió en , donde es el número de factores irreducibles del polinomio. Por lo tanto, el algoritmo no era polinomial y no era práctico cuando el número primo era lo suficientemente grande. En 1969, este problema fue resuelto por Hans Zassenhaus , quien mostró cómo reducir el cuello de botella del algoritmo al problema de encontrar las raíces de algún polinomio [4] . En 1970 se volvió a publicar el artículo de Berlekamp, teniendo en cuenta las soluciones de Zassenhaus [1] . $O(n^{3}+prn)$ $r$ $pags$

En 1980, Michael Rabin llevó a cabo un análisis riguroso del algoritmo, lo generalizó para trabajar con campos finitos de la forma y demostró que la probabilidad de error de una iteración del algoritmo no supera [2] , y en 1981 Michael Ben- O reforzó esta estimación a , donde — el número de raíces diferentes del polinomio [8] . La cuestión de la existencia de un algoritmo determinista de polinomios para encontrar las raíces de un polinomio sobre un campo finito sigue abierta: los principales algoritmos de factorización de polinomios , el algoritmo de Berlekamp y el algoritmo de Cantor-Zassenhaus son probabilísticos. En 1981, Paul Camion demostró [9] que tal algoritmo existe para cualquier número dado , pero este resultado es puramente teórico y la cuestión de la posibilidad de construir los conjuntos descritos por él en la práctica permanece abierta [10] . ${\mathbb F}_{{p^{k))}$ $1/2$ ${\textstyle 1-1/2^{k-1}+O\left(1/{\sqrt {p}}\right)}$ $k$ $f(x)$ $pags$

En la primera edición del segundo volumen de "El arte de la programación " sobre algoritmos numéricos, Donald Knuth escribe que en 1960 se conocían procedimientos de factorización similares, pero rara vez se encontraban en el dominio público [4] . Uno de los primeros ejemplos publicados del uso del método se puede encontrar en el trabajo de Golomb , Welsh y Hales de 1959 sobre la factorización de trinomios sobre , donde se consideró un caso especial [11] . $\mathbb {F} _{2}$ ${\ estilo de visualización p = 2, z = 1}$

Algoritmo

Planteamiento del problema

Sea un número primo impar. Considere un polinomio sobre el campo de residuos módulo . Es necesario encontrar todos los números tales que para todos los posibles [2] [12] . $pags$ ${\textstyle f(x)=a_{0}+a_{1}x+\dots +a_{n}x^{n))$ $\mathbb {Z} _{p}$ $pags$ ${\ estilo de visualización \ lambda _ {1}, \ puntos, \ lambda _ {k}}$ ${\textstyle f(\lambda _{i})\equiv 0{\pmod {p))}$ $i$

Aleatorización

deja _ Encontrar todas las raíces de tal polinomio es equivalente a dividirlo en factores lineales. Para encontrar una partición de este tipo, es suficiente aprender a dividir el polinomio en dos factores cualesquiera y luego ejecutarlos recursivamente. Para ello, introducimos un polinomio , donde es un número aleatorio de . Si tal polinomio puede representarse como un producto , entonces en términos del polinomio original esto significa que , lo que da una factorización del polinomio original [1] [12] . ${\textstyle f(x)=(x-\lambda _{1})(x-\lambda _{2})\puntos (x-\lambda _{n})}$ ${\textstyle f_{z}(x)=f(xz)=(x-\lambda_{1}-z)(x-\lambda_{2}-z)\dots (x-\lambda_{n) }-z)}$ $z$ $\mathbb {Z} _{p}$ $f_{z}(x)=p_{0}(x)p_{1}(x)$ $f(x)=p_{0}(x+z)p_{1}(x+z)$ $f(x)$

Clasificación de elementos $\mathbb {F} _{p}$

Según el criterio de Euler, para cualquier monomio se cumple exactamente una de las siguientes propiedades [1] : ${\ estilo de visualización (x-\ lambda)}$

El monomio es igual a si , $X$ $\lambda=0$
El monomio se divide si es un residuo cuadrático módulo , ${\textstyle g_{0}(x)=(x^{(p-1)/2}-1)}$ $\lambda$ $pags$
El monomio se divide si es un módulo cuadrático no residual este. ${\textstyle g_{1}(x)=(x^{(p-1)/2}+1)}$ $\lambda$

Por tanto, si no es divisible por , lo que se puede comprobar por separado, entonces es igual al producto de los máximos comunes divisores y [12] . ${\ estilo de visualización f_ {z} (x)}$ $X$ ${\ estilo de visualización f_ {z} (x)}$ ${\ estilo de visualización \ gcd (f_ {z} (x); g_ {0} (x))}$ ${\ estilo de visualización \ gcd (f_ {z} (x); g_ {1} (x))}$

Método Berlekamp

Lo anterior conduce al siguiente algoritmo [1] :

Los coeficientes del polinomio se calculan explícitamente , ${\ Displaystyle f_ {z} (x) = f (xz)}$
Calcular el resto de la división elevando al cuadrado sucesivamente y tomando el resto de , ${\textstyle x,x^{2},x^{2^{2)),x^{2^{3)),x^{2^{4)),\dots,x^{2^{ \lpiso \log _{2}p\rpiso }}}$ ${\ estilo de visualización f_ {z} (x)}$ ${\ estilo de visualización f_ {z} (x)}$
La exponenciación binaria calcula el resto de la división utilizando los polinomios calculados en el último paso, ${\textstyle x^{(p-1)/2}}$ ${\ estilo de texto f_ {z} (x)}$
Si , entonces lo anterior da una factorización no trivial , ${\textstyle x^{(p-1)/2}\no \equiv \pm 1{\pmod {f_{z}(x)))}$ ${\ estilo de visualización \ gcd}$ ${\ estilo de visualización f_ {z} (x)}$
De lo contrario, todas las raíces son residuos o no residuos al mismo tiempo y vale la pena probar con otro valor . ${\ estilo de visualización f_ {z} (x)}$ $z$

Si además se divide por algún polinomio que no tiene raíces en , entonces al calcular con y , se obtendrá una partición del polinomio libre de cuadrados en factores no triviales, por lo que el algoritmo permite encontrar todas las raíces de cualquier polinomios sobre , y no solo aquellos que se descomponen en un producto de monomios [12] . $f(x)$ $g(x)$ $\mathbb {Z} _{p}$ ${\ estilo de visualización \ gcd}$ $g_{0}(x)$ ${\ estilo de visualización g_ {1} (x)}$ $f_{z}(x)/g_{z}(x)$ $\mathbb {Z} _{p}$

Extrayendo la raíz cuadrada

Sea necesario resolver una comparación cuyas soluciones sean los elementos y respectivamente. Encontrarlos es equivalente a factorizar un polinomio sobre un campo . En este caso particular, el problema se simplifica, ya que para la solución basta con calcular solamente . Para el polinomio resultante, exactamente una de las declaraciones será verdadera: ${\textstyle x^{2}\equiv a{\pmod {p}}}$ $\beta$ ${\ estilo de visualización - \ beta}$ ${\textstyle f(x)=x^{2}-a=(x-\beta)(x+\beta)}$ $\mathbb {Z} _{p}$ ${\ estilo de visualización \ gcd (f_ {z} (x); g_ {0} (x))}$

GCD es , lo que implica que y son no residuos cuadráticos al mismo tiempo, $una$ $z+\beta$ $z-\beta$
MCD es , lo que implica que ambos números son residuos cuadráticos, ${\ estilo de visualización f_ {z} (x)}$
GCD es igual a un monomio , lo que implica que exactamente un número de dos es un residuo cuadrático. ${\ estilo de visualización (xt)}$

En el tercer caso, el monomio resultante debe ser igual a o , o . Esto permite escribir la solución como [1] . ${\ estilo de visualización (xz-\ beta)}$ ${\ estilo de visualización (x-z + \ beta)}$ ${\estilo de texto \beta =(tz){\pmod {p}}}$

Ejemplo

Resolvamos la comparación . Para hacer esto, necesitas factorizar . Consideremos los valores posibles : ${\textstyle x^{2}\equiv 5{\pmod {11}}}$ $f(x)=x^{2}-5=(x-\beta)(x+\beta )$ $z$

deja _ Entonces de donde . Ambos números no son residuos y debe tomar otro . ${\ estilo de visualización z = 3}$ $f_{z}(x)=(x-3)^{2}-5=x^{2}-6x+4$ ${\displaystyle\gcd(x^{2}-6x+4;x^{5}-1)=1}$ $3\pm\beta$ $z$

deja _ Entonces de donde . Por lo tanto , por lo tanto . ${\ estilo de visualización z = 2}$ $f_{z}(x)=(x-2)^{2}-5=x^{2}-4x-1$ ${\textstyle \gcd(x^{2}-4x-1;x^{5}-1)\equiv x-9{\pmod {11))}$ ${\textstyle x-9=x-2-\beta}$ $\beta \equiv 7{\pmod {11}}$ ${\textstyle -\beta \equiv -7\equiv 4{\pmod {11}}}$

La verificación muestra eso y es válida . ${\textstyle 7^{2}\equiv 49\equiv 5{\pmod {11}}}$ ${\textstyle 4^{2}\equiv 16\equiv 5{\pmod {11))}$

Justificación del método

El algoritmo encuentra una partición en factores no triviales en todos los casos, excepto en aquellos en los que todos los números son residuos o no residuos al mismo tiempo. De acuerdo con la teoría de la ciclotomía [1] , la probabilidad de tal evento para el caso en que ambos son residuos o no residuos al mismo tiempo (es decir, cuando no es adecuado para nuestro procedimiento) se puede estimar como [8] , donde es el número de números diferentes entre [1] . Por lo tanto, la probabilidad de error del algoritmo no excede . ${\ estilo de visualización f_ {z} (x)}$ ${\displaystyle z+\lambda _{1},z+\lambda _{2},\puntos,z+\lambda _{n))$ ${\ estilo de visualización \ lambda _ {1}, \ puntos, \ lambda _ {n}}$ $z=0$ ${\ estilo de visualización 1/2 ^ {k-1}}$ $k$ ${\ estilo de visualización \ lambda _ {1}, \ puntos, \ lambda _ {n}}$ $1/2$

Aplicación a la factorización de polinomios

Se sabe por la teoría de campos finitos que si el grado de un polinomio irreducible es , entonces dicho polinomio es un divisor y no un divisor de . $q(x)$ $d$ ${\ estilo de visualización x^{p^{d}}-x}$ ${\ estilo de visualización x^{p^{t}}-x}$ ${\ estilo de visualización t<d}$

Así, considerando secuencialmente los polinomios donde y para , podemos dividir el polinomio en factores de la forma , donde es el producto de todos los polinomios irreducibles de grado que dividen el polinomio . Conociendo el grado de , podemos determinar el número de tales polinomios igual a . deja _ Si consideramos el polinomio , donde , entonces el orden de tal polinomio en el campo debe dividir el número . Si no es divisible por , entonces el polinomio es divisible pero no por . $h_{i}(x)=\gcd(f_{i}(x),x^{p^{i}}-1)$ ${\ Displaystyle f_ {1} (x) = f (x)}$ $f_{i}(x)=f_{i-1}(x)/h_{i-1}(x)$ $yo>1$ $f(x)$ $f(x)=h_{1}(x)\puntos h_{n}(x)$ $h_{i}(x)$ $i$ $f(x)$ $h_{i}(x)$ $r_{i}=\grados h_{i}(x)/i$ $h_{i}(x)=p_{1}(x)\puntos p_{r_{i}}(x)$ $p_{j}(xz)$ ${\textstyle z\in \mathbb {F} _{p}}$ $DJ}$ ${\ estilo de texto \ mathbb {F} _ {p^ {i}}}$ $p^{i}-1$ $DJ}$ $d_{k}$ ${\textstyle x^{d_{j}}-x}$ ${\ estilo de texto p_ {j} (xz)}$ ${\ estilo de texto p_ {k} (xz)}$

Con base en esto, Zassenhaus sugirió buscar divisores de un polinomio en la forma , donde hay algún divisor suficientemente grande , por ejemplo, . En un caso particular , se obtiene exactamente el método de Berlekamp como se describe anteriormente [4] . $h_{i}(xz)$ ${\estilo de texto \gcd(h_{i}(xz),x^{f}-1)}$ $F$ $p^{i}-1$ ${\textstyle f={\frac {p^{i}-1}{2}}}$ $yo=1$

Horario de apertura

Paso a paso, el tiempo de ejecución de una iteración del algoritmo se puede estimar de la siguiente manera, asumiendo que el grado del polinomio es : $norte$

Considerando que según la fórmula binomial de Newton , la transición de a se realiza en , ${\textstyle (xz)^{k}=\sum \limits _{i=0}^{k}{\binom {k}{i}}(-z)^{ki}x^{i}}$ $f(x)$ ${\ estilo de visualización f (xz)}$ $O(n^{2})$
El producto de polinomios y tomar el resto de un polinomio módulo otro se realiza en , por lo que el cálculo se realiza en , ${\ estilo de texto O (n ^ {2})}$ ${\textstyle x^{2^{k}}{\bmod {f}}_{z}(x)}$ ${\textstyle O(n^{2}\log p)}$
Similar al punto anterior, la exponenciación binaria se realiza en , $O(n^{2}\log p)$
La extracción de dos polinomios según el algoritmo de Euclides se realiza en . ${\ estilo de visualización \ gcd}$ $O(n^{2})$

Por lo tanto, se puede realizar una iteración del algoritmo para operaciones aritméticas con elementos , y encontrar todas las raíces del polinomio requiere un promedio [8] . En el caso particular de extraer la raíz cuadrada, el valor es dos, por lo que el tiempo de ejecución se estima como una iteración del algoritmo [12] . $O(n^{2}\log p)$ $\mathbb {F} _{p}$ $O(n^{2}\log n\log p)$ $norte$ ${\ estilo de visualización O (\ log p)}$

Notas

↑ 1 2 3 4 5 6 7 8 9 10 11 Berlekamp ER Factorización de polinomios sobre grandes campos finitos // Matemáticas de computación. - 1970. - vol. 24 , edición. 111 . - Pág. 730-732 . — ISSN 0025-5718 . -doi : 10.1090 / S0025-5718-1970-0276200-X .
↑ 1 2 3 4 5 Rabin M. Algoritmos probabilísticos en campos finitos // SIAM Journal on Computing. - 1980. - 1 de mayo ( vol. 9 , ns. 2 ). - pág. 273-280 . — ISSN 0097-5397 . -doi : 10.1137/ 0209024 . Archivado desde el original el 23 de junio de 2019.
↑ 1 2 Berlekamp ER Factorización de polinomios sobre campos finitos // The Bell System Technical Journal. - 1967. - Octubre ( vol. 46 , ns. 8 ). - Pág. 1853-1859 . — ISSN 0005-8580 . -doi : 10.1002 / j.1538-7305.1967.tb03174.x . Archivado desde el original el 17 de febrero de 2019.
↑ 1 2 3 4 5 Knuth DE El arte de la programación informática . - Reading, Massachusetts: Addison-Wesley Publishing Company, 1968. - Vol. 2.- Págs. 381-390. — 624 pág. - ISBN 0-201-03802-1 . Archivado el 3 de agosto de 2019 en Wayback Machine .
↑ Sze TW Sobre sacar raíces cuadradas sin residuos cuadráticos sobre campos finitos // Matemáticas de computación. - 2011. - 3 de enero ( vol. 80 , ns. 275 ). - Pág. 1797-1811 . — ISSN 0025-5718 . -doi : 10.1090/ s0025-5718-2011-02419-1 .
↑ Peralta R. Un algoritmo probabilístico simple y rápido para calcular raíces cuadradas módulo a número primo (Corresp. ) // IEEE Transactions on Information Theory. - 1986. - noviembre ( vol. 32 , núm. 6 ). - P. 846-847 . — ISSN 0018-9448 . -doi : 10.1109/ TIT.1986.1057236 . Archivado desde el original el 30 de junio de 2019.
↑ Padró C., Sáez G. Raíces cúbicas en Zm // Letras de Matemática Aplicada. - 2002. - agosto ( vol. 15 , ns. 6 ). - P. 703-708 . — ISSN 0893-9659 . - doi : 10.1016/s0893-9659(02)00031-9 .
↑ 1 2 3 Ben-Or M. Algoritmos probabilísticos en campos finitos // 22.º Simposio anual sobre fundamentos de la informática (sfcs 1981). - 1981. - Octubre. - P. 394-398 . -doi : 10.1109/ SFCS.1981.37 . Archivado desde el original el 29 de julio de 2019.
↑ Camion P. Un algoritmo determinista para factorizar polinomios de Fq [X] // Matemáticas combinatorias, Actas del Coloquio internacional sobre teoría de grafos y combinatoria. - Elsevier, 1983. - P. 149-157 . — ISBN 9780444865120 .
↑ Grenet B., van der Hoeven J., Lecerf G. Hallazgo de raíces deterministas sobre campos finitos usando transformadas de Graeffe // Álgebra aplicable en ingeniería, comunicación y computación. - 2015. - Vol. 27 , edición. 3 . — Pág. 239 . — ISSN 0938-1279 . -doi : 10.1007/ s00200-015-0280-5 .
↑ Golomb SW, Hales A., Welch LR Sobre la factorización de trinomios sobre GF(2 ) // Shift Register Sequences. - World Scientific, 2017. - Marzo. - Pág. 90-108. - ISBN 978-981-4632-00-3 . -doi : 10.1142/ 9789814632010_0005 .
↑ 1 2 3 4 5 Menezes AJ, Blake IF, Gao XH, Mullin RC, Vanstone SA Aplicaciones de campos finitos . - Springer EE.UU., 1993. - P. 22-26. — 218p. - (La Serie Internacional Springer en Ingeniería y Ciencias de la Computación). — ISBN 9780792392828 . Archivado el 30 de junio de 2019 en Wayback Machine .

Algoritmos de teoría de números
Pruebas de simplicidad	Molinero Miller - Rabín Luca-Lemaire pepina Agrawala - Kayala - Sajonia Ruiseñor - Strassen
Encontrar números primos	Iterando sobre divisores Tamiz de Eratóstenes tamiz de atkin Tamiz Sundarama
Factorización	Iterando sobre divisores método Fermat p −1 Método de Pollard Algoritmo ρ de Pollard método Lehmann Método de la curva elíptica (algoritmo de Lenstra) algoritmo de dixon tamiz cuadrado
logaritmo discreto	Algoritmo de Gelfond-Shanks Algoritmo de Polig-Hellman Método ρ de Pollard Algoritmo del canguro de Pollard algoritmo de Adleman algoritmo COS
Encontrar MCD	Algoritmo de Euclides Algoritmo avanzado Algoritmo binario
Módulo aritmético	algoritmo de Montgomery Teorema del resto chino
Multiplicación y división de números.	Algoritmo Karatsuba Algoritmo de Toom-Cook Algoritmo de Schönhage-Strassen Algoritmo del Führer Algoritmo de Harvey-van der Hoeven Algoritmo de Burnickel-Ziegler
Calcular la raíz cuadrada	Algoritmo de Tonelli-Shanks Algoritmo de Berlekamp-Rabin