Algoritmo de Berlekamp-Rabin

En teoría de números , el algoritmo de búsqueda de raíces de Berlekamp , ​​también llamado algoritmo de Berlekamp-Rabin , es el método probabilístico para encontrar raíces de polinomios sobre un cuerpo con elementos. El método fue descubierto por Elwyn Berlekamp en 1970 ^[1] como un auxiliar del algoritmo para la factorización de polinomios sobre cuerpos finitos. El algoritmo fue modificado posteriormente por Rabin para cuerpos finitos arbitrarios en 1979. ^[2] El método también fue descubierto independientemente antes de Berlekamp por otros investigadores. ^[3]${\displaystyle \mathbb {F}_{p}}$${\estilo de visualización p}$

El método fue propuesto por Elwyn Berlekamp en su trabajo de 1970 ^[1] sobre factorización polinómica sobre cuerpos finitos. Su trabajo original carecía de una prueba de corrección formal ^[2] y luego fue refinado y modificado para cuerpos finitos arbitrarios por Michael Rabin . ^[2] En 1986 René Peralta propuso un algoritmo similar ^[4] para encontrar raíces cuadradas en . ^[5] En 2000, el método de Peralta se generalizó para ecuaciones cúbicas . ^[6]${\displaystyle \mathbb {F}_{p}}$

Sea un número primo impar. Consideremos el polinomio sobre el cuerpo de residuos módulo . El algoritmo debería encontrar todos los en tales que en . ^{[2] [7]}${\estilo de visualización p}$${\textstyle f(x)=a_{0}+a_{1}x+\cdots +a_{n}x^{n}}$${\displaystyle \mathbb {F} _{p}\simeq \mathbb {Z} /p\mathbb {Z} }$${\estilo de visualización p}$${\estilo de visualización \lambda}$${\displaystyle \mathbb {F}_{p}}$${\textstyle f(\lambda )=0}$${\displaystyle \mathbb {F}_{p}}$

Sea . Encontrar todas las raíces de este polinomio es equivalente a encontrar su factorización en factores lineales. Para encontrar dicha factorización es suficiente dividir el polinomio en dos divisores no triviales y factorizarlos recursivamente. Para ello, considere el polinomio donde  es algún elemento de . Si uno puede representar este polinomio como el producto , entonces en términos del polinomio inicial significa que , lo que proporciona la factorización necesaria de . ^{[1] [7]}${\textstyle f(x)=(x-\lambda _{1})(x-\lambda _{2})\cdots (x-\lambda _{n})}$${\textstyle f_{z}(x)=f(xz)=(x-\lambda _{1}-z)(x-\lambda _{2}-z)\cdots (x-\lambda _{n}-z)}$${\estilo de visualización z}$${\displaystyle \mathbb {F}_{p}}$${\displaystyle f_{z}(x)=p_{0}(x)p_{1}(x)}$${\displaystyle f(x)=p_{0}(x+z)p_{1}(x+z)}$${\estilo de visualización f(x)}$

Debido al criterio de Euler , para cada monomio se cumple exactamente una de las siguientes propiedades: ^[1]${\estilo de visualización (x-\lambda)}$

1. El monomio es igual a si ,${\estilo de visualización x}$${\displaystyle \lambda = 0}$
2. El monomio se divide si  es residuo cuadrático módulo ,${\textstyle g_{0}(x)=(x^{(p-1)/2}-1)}$${\estilo de visualización \lambda}$${\estilo de visualización p}$
3. El monomio se divide si  es cuadrático no residual módulo .${\textstyle g_{1}(x)=(x^{(p-1)/2}+1)}$${\estilo de visualización \lambda}$${\estilo de visualización p}$

Por lo 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 . ^[7]$Estilo de visualización f_ {z}(x)}$${\estilo de visualización x}$$Estilo de visualización f_ {z}(x)}$ ${\displaystyle \mcd(f_{z}(x);g_{0}(x))}$${\displaystyle \mcd(f_{z}(x);g_{1}(x))}$

La propiedad anterior conduce al siguiente algoritmo: ^[1]

1. Calcular explícitamente los coeficientes de ,${\displaystyle f_{z}(x)=f(xz)}$
2. Calcular los residuos del módulo elevando al cuadrado el polinomio actual y tomando el residuo módulo ,${\textstyle x,x^{2},x^{2^{2}},x^{2^{3}},x^{2^{4}},\ldots ,x^{2^{\lfloor \log _{2}p\rfloor }}}$$Estilo de visualización f_ {z}(x)}$$Estilo de visualización f_ {z}(x)}$
3. Usando la exponenciación por cuadrado y los polinomios calculados en los pasos anteriores, calcule el resto del módulo ,${\textstyle x^{(p-1)/2}}$${\textstyle f_{z}(x)}$
4. Si a continuación se menciona una factorización no trivial de ,${\textstyle x^{(p-1)/2}\no \equiv \pm 1{\pmod {f_{z}(x)}}}$${\displaystyle \mcd}$$Estilo de visualización f_ {z}(x)}$
5. De lo contrario, todas las raíces de son residuos o no residuos simultáneamente y uno tiene que elegir otro .$Estilo de visualización f_ {z}(x)}$${\estilo de visualización z}$

Si es divisible por algún polinomio primitivo no lineal sobre entonces al calcular con y se obtendrá una factorización no trivial de , por lo que el algoritmo permite encontrar todas las raíces de polinomios arbitrarios sobre . ${\estilo de visualización f(x)}$ ${\estilo de visualización g(x)}$${\displaystyle \mathbb {F}_{p}}$${\displaystyle \mcd}$$Estilo de visualización g_{0}(x)}$$Estilo de visualización g_{1}(x)}$${\displaystyle f_{z}(x)/g_{z}(x)}$${\displaystyle \mathbb {F}_{p}}$

Consideremos una ecuación que tiene como raíces los elementos y . La solución de esta ecuación es equivalente a la factorización del polinomio sobre . En este caso particular, basta con calcular solo . Para este polinomio se cumplirá exactamente una de las siguientes propiedades: ${\textstyle x^{2}\equiv a{\pmod {p}}}$${\estilo de visualización \beta}$${\estilo de visualización -\beta}$${\textstyle f(x)=x^{2}-a=(x-\beta )(x+\beta )}$${\displaystyle \mathbb {F}_{p}}$${\displaystyle \mcd(f_{z}(x);g_{0}(x))}$

1. MCD es igual a lo que significa que y son ambos residuos cuadráticos no válidos.${\estilo de visualización 1}$${\estilo de visualización z+\beta}$${\displaystyle z-\beta}$
2. MCD es igual a lo que significa que ambos números son residuos cuadráticos,$Estilo de visualización f_ {z}(x)}$
3. MCD es igual a lo que significa que exactamente uno de estos números es residuo cuadrático.${\estilo de visualización (xt)}$

En el tercer caso, el MCD es igual a o . Esto permite escribir la solución como . ^[1]${\estilo de visualización (xz-\beta )}$${\displaystyle (x-z+\beta )}$${\textstyle \beta =(tz){\pmod {p}}}$

Supongamos que necesitamos resolver la ecuación . Para ello, necesitamos factorizar . Consideremos algunos valores posibles de : ${\textstyle x^{2}\equiv 5{\pmod {11}}}$${\displaystyle f(x)=x^{2}-5=(x-\beta )(x+\beta )}$${\estilo de visualización z}$

1. Sea . Entonces , por lo tanto . Ambos números son residuos cuadráticos no válidos, por lo que necesitamos tomar algún otro .${\displaystyle z=3}$${\displaystyle f_{z}(x)=(x-3)^{2}-5=x^{2}-6x+4}$${\displaystyle \mcd(x^{2}-6x+4;x^{5}-1)=1}$${\displaystyle 3\pm\beta}$${\estilo de visualización z}$

1. Sea . Entonces , por lo tanto . De esto se sigue , por lo que y .${\displaystyle z=2}$${\displaystyle f_{z}(x)=(x-2)^{2}-5=x^{2}-4x-1}$${\textstyle \mcd(x^{2}-4x-1;x^{5}-1)\equiv x-9{\pmod {11}}}$${\textstyle x-9=x-2-\beta }$${\displaystyle \beta \equiv 7{\pmod {11}}}$${\textstyle -\beta \equiv -7\equiv 4{\pmod {11}}}$

Una comprobación manual muestra que, efectivamente, y . ${\textstyle 7^{2}\equiv 49\equiv 5{\pmod {11}}}$${\textstyle 4^{2}\equiv 16\equiv 5{\pmod {11}}}$

El algoritmo encuentra la factorización de en todos los casos excepto en aquellos en los que todos los números son residuos cuadráticos o no residuos simultáneamente. Según la teoría de la ciclotomía, ^[8] la probabilidad de tal evento para el caso en el que son todos los residuos o no residuos simultáneamente (es decir, cuando fallaría) puede estimarse como donde  es el número de valores distintos en . ^[1] De esta manera, incluso para el peor caso de y , la probabilidad de error puede estimarse como y para el caso de raíz cuadrada modular la probabilidad de error es como máximo . ${\displaystyle f_{z}(x)}$${\displaystyle z+\lambda _{1},z+\lambda _{2},\ldots ,z+\lambda _{n}}$${\displaystyle \lambda _{1},\ldots ,\lambda _{n}}$${\displaystyle z=0}$${\displaystyle 2^{-k}}$${\displaystyle k}$${\displaystyle \lambda _{1},\ldots ,\lambda _{n}}$${\displaystyle k=1}$${\displaystyle f(x)=(x-\lambda )^{n}}$${\displaystyle 1/2}$${\displaystyle 1/4}$

Sea un polinomio de grado . Derivamos la complejidad del algoritmo de la siguiente manera: ${\displaystyle n}$

1. Debido al teorema binomial , podemos realizar la transición de a en el tiempo.${\textstyle (x-z)^{k}=\sum \limits _{i=0}^{k}{\binom {k}{i}}(-z)^{k-i}x^{i}}$${\displaystyle f(x)}$${\displaystyle f(x-z)}$${\displaystyle O(n^{2})}$
2. La multiplicación de polinomios y la toma del resto de un polinomio módulo otro se puede hacer en , por lo tanto, el cálculo de se realiza en .${\textstyle O(n^{2})}$${\textstyle x^{2^{k}}{\bmod {f}}_{z}(x)}$${\textstyle O(n^{2}\log p)}$
3. La exponenciación binaria funciona en .${\displaystyle O(n^{2}\log p)}$
4. Tomando el de dos polinomios a través del algoritmo euclidiano funciona en .${\displaystyle \gcd }$${\displaystyle O(n^{2})}$

Por lo tanto, todo el procedimiento puede realizarse en . Utilizando la transformada rápida de Fourier y el algoritmo Half-GCD, ^[9] la complejidad del algoritmo puede mejorarse a . Para el caso de raíz cuadrada modular, el grado es , por lo que la complejidad total del algoritmo en tal caso está limitada por por iteración. ^[7]${\displaystyle O(n^{2}\log p)}$${\displaystyle O(n\log n\log pn)}$${\displaystyle n=2}$${\displaystyle O(\log p)}$