Algoritmo de Cantor-Zassenhaus

En álgebra computacional, el algoritmo de Cantor–Zassenhaus es un método para factorizar polinomios sobre cuerpos finitos (también llamados cuerpos de Galois).

El algoritmo consiste principalmente en cálculos de exponenciación y MCD polinomial. Fue inventado por David G. Cantor y Hans Zassenhaus en 1981.

Podría decirse que es el algoritmo dominante para resolver el problema, habiendo reemplazado al algoritmo de Berlekamp de 1967. Actualmente se encuentra implementado en muchos sistemas de álgebra computacional.

El algoritmo Cantor–Zassenhaus toma como entrada un polinomio libre de cuadrado ${\displaystyle f(x)}$ (es decir, uno sin factores repetidos) de grado n con coeficientes en un campo finito ${\displaystyle \mathbb {F} _{q}$ cuyos factores polinomios irreducibles son todos de igual grado (existen algoritmos para tener en cuenta eficazmente los polinomios arbitrarios en un producto de polinomios que satisfagan estas condiciones, por ejemplo, ${\displaystyle f(x)/\gcd(f(x),f'(x)}$ es un polinomio libre de cuadrado con los mismos factores ${\displaystyle f(x)}$, para que el algoritmo Cantor-Zassenhaus pueda ser utilizado para factorar polinomios arbitrarios). Da como salida un polinomio ${\displaystyle g(x)}$ con coeficientes en el mismo campo, ${\displaystyle g(x)}$ divideciones ${\displaystyle f(x)}$. El algoritmo puede ser aplicado recursivamente a estos y posteriores divisores, hasta que encontremos la descomposición de ${\displaystyle f(x)}$ en poderes de polinomios irreducibles (recalling que el anillo de polinomios sobre cualquier campo es un dominio de factorización único).

Todos los factores posibles ${\displaystyle f(x)}$ están contenidos en el anillo factorial ${\displaystyle R={\frac {\f} {\f}{q}{\langle f(x)\rangle }}}}$. Si suponemos eso ${\displaystyle f(x)}$ tiene factores irreducibles ${\displaystyle p_{1}(x),p_{2}(x),\ldotsp_{s}(x)}$, todo el grado d, entonces este anillo factor es isomorfo al producto directo de anillos de factor ${\displaystyle S=\prod ¿Por qué?$. El isomorfismo de R a S, di ${\displaystyle \phi }$, mapas un polinomio ${\displaystyle g(x)\in R}$ a la s-tuple de sus reducciones modulo cada uno de los ${\displaystyle p_{i}(x)}$, es decir, si:

${\fnMicrosoft Sans Serif} {\fnMicrosoft Sans Serif} {\fnMicrosoft Sans Serif} {\fnMicrosoft Sans Serif} {\fnMicrosoft Sans Serif} {\fnMicrosoft Sans Serif} {\fnMicrosoft ] {\fnMicrosoft Sans Serif} {\fnMicrosoft} {\f} {\fnMicrosoft Sans Serif} {\fnMicrosoft Sans Serif} {\fnMicrosoft Sans Serif} {\fnMicrosoft Sans)} {\fnMicrosoft Sans Serif}\fnMicrosoft Sans)} {\fnMicrosoft Sans} {\fnMicrosoft Sans)} {\fnMicrosoft Sans} {\fnMicrosoft Sans Serif} {\fnMicrosoft Sans) {\fnMicrosoft Sans}\fnMicrosoft Sans Serif} {\fnMicrosoft Sans$

entonces ${\displaystyle \phi (g(x)+\langle f(x)\rangle)=(g_{1}(x)+\langle p_{1}(x)\rangle\ldotsg_{s}(x)+\langle p_{s}(x)\rangle)}}}$. Es importante señalar lo siguiente en este punto, ya que será de importancia crítica más adelante en el algoritmo: Desde ${\displaystyle p_{i}(x)}$ son cada uno irreducible, cada uno de los anillos factor en esta suma directa es de hecho un campo. Estos campos tienen grado ${\displaystyle q^{d}$.

El resultado básico subyacente al algoritmo Cantor-Zassenhaus es el siguiente: Si ${\displaystyle a(x)\in R}$ es una satisfacción polinomio:

${\displaystyle a(x)\neq 0,\pm 1}$

${\displaystyle a_{i}(x)\in \{0,-1,1\}{\text{ for }i=1,2,\ldotss,}$

Donde ${\displaystyle a_{i}(x)}$ es la reducción de ${\displaystyle a(x)}$ modulo ${\displaystyle p_{i}(x)}$ como antes, y si alguno de los dos de los tres siguientes conjuntos es no vacío:

${\displaystyle A=\{i\mid a_{i}(x)=0\}$

${\displaystyle B=\{i\mid a_{i}(x)=-1\}$

${\displaystyle C=\{i\mid a_{i}(x)=1\}$

entonces existen los siguientes factores no-triviales ${\displaystyle f(x)}$:

${\displaystyle \gcd(f(x),a(x)=\prod _{i\in A}p_{i}(x),}$

${\displaystyle \gcd(f(x),a(x)+1)=\prod _{i\in B}p_{i}(x),}$

${\displaystyle \gcd(f(x),a(x)-1)=\prod _{i\in C}p_{i}(x). }$

El algoritmo Cantor-Zassenhaus compute polinomios del mismo tipo que ${\displaystyle a(x)}$ arriba usando el isomorfismo discutido en la sección Antecedentes. Procede como sigue, en el caso en que el campo ${\displaystyle \mathbb {F} _{q}$ es de carácter extraño (el proceso puede ser generalizado a 2 campos característicos de manera bastante sencilla. Seleccione un polinomio aleatorio ${\displaystyle b(x)\in R}$ tales que ${\displaystyle b(x)\neq 0,\pm 1}$. Set ${\displaystyle m=(q^{d}-1)/2}$ y computación ${\displaystyle b(x)} {m}$. Desde ${\displaystyle \phi }$ es un isomorfismo, tenemos (utilizando nuestra notación ya establecida):

${\displaystyle \phi (b(x)^{m})=(b_{1}{m}(x)+\langle p_{1}(x)\rangle\ldotsb_{s}^{m}(x)+\langle p_{s}(x)\rangle).}}$

Ahora, cada uno ${\displaystyle b_{i}(x)+\langle p_{i}(x)\rangle }$ es un elemento de un campo de orden ${\displaystyle q^{d}$, como se señaló anteriormente. El subgrupo multiplicativo de este campo tiene orden ${\displaystyle q^{d}-1}$ a menos que ${\displaystyle b_{i}(x)=0}$, tenemos ${\displaystyle b_{i}(x)}{q^{d}=1}$ para cada uno i y por consiguiente ${\displaystyle b_{i}(x)^{m}=\pm 1}$ para cada uno i. Si ${\displaystyle b_{i}(x)=0}$, entonces por supuesto ${\displaystyle b_{i}(x)}{m}=0}$. Por lo tanto ${\displaystyle b(x)} {m}$ es un polinomio del mismo tipo que ${\displaystyle a(x)}$ arriba. Además, desde entonces ${\displaystyle b(x)\neq 0,\pm 1}$, al menos dos de los sets ${\displaystyle A,B}$ y C son indeseables y al computar los GCD anteriores podemos obtener factores no-triviales. Dado que el anillo de polinomios sobre un campo es un dominio euclidiano, podemos calcular estos GCD utilizando el algoritmo euclidiano.

Una aplicación importante del algoritmo de Cantor-Zassenhaus es el cálculo de logaritmos discretos sobre cuerpos finitos de orden primo-potencial. El cálculo de logaritmos discretos es un problema importante en la criptografía de clave pública. Para un cuerpo de orden primo-potencial, el método más rápido conocido es el método de cálculo de índices, que implica la factorización de los elementos del cuerpo. Si representamos el cuerpo de orden primo-potencial de la forma habitual (es decir, como polinomios sobre el cuerpo base de orden primo, reducido módulo un polinomio irreducible de grado apropiado), entonces esto es simplemente la factorización polinómica, como la que proporciona el algoritmo de Cantor-Zassenhaus.

El algoritmo de Cantor–Zassenhaus se implementa en el sistema de álgebra computacional PARI/GP como la función factorcantor().

• Factorización polinómica
• Factorización de polinomios sobre campos finitos

• https://web.archive.org/web/20200301213349/http://blog.fkraiem.org/2013/12/01/polynomial-factorisation-over-finite-fields-part-3-final-splitting-cantor-zassenhaus-in-odd-characteristic/