Algoritmo de Berlekamp-Rabin

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

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

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

Por lo tanto, si${\displaystyle f_{z}(x)}$no es divisible por${\displaystyle x}$, que puede comprobarse por separado, entonces${\displaystyle f_{z}(x)}$es igual al producto de los máximos comunes divisores${\displaystyle \gcd(f_{z}(x);g_{0}(x))}$y${\displaystyle \gcd(f_{z}(x);g_{1}(x))}$. ^{[ 7 ]}

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

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

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

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

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

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

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

1. Dejar${\displaystyle z=3}$. Entonces${\displaystyle f_{z}(x)=(x-3)^{2}-5=x^{2}-6x+4}$, de este modo${\displaystyle \gcd(x^{2}-6x+4;x^{5}-1)=1}$Ambos números${\displaystyle 3\pm \beta }$son no residuos cuadráticos, por lo que necesitamos tomar algún otro${\displaystyle z}$.

1. Dejar${\displaystyle z=2}$. Entonces${\displaystyle f_{z}(x)=(x-2)^{2}-5=x^{2}-4x-1}$, de este modo${\textstyle \gcd(x^{2}-4x-1;x^{5}-1)\equiv x-9{\pmod {11}}}$De esto se deduce${\textstyle x-9=x-2-\beta }$, entonces${\displaystyle \beta \equiv 7{\pmod {11}}}$y${\textstyle -\beta \equiv -7\equiv 4{\pmod {11}}}$.

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