Algoritmo de Cantor-Zassenhaus

Algoritmo para factorizar polinomios en campos finitos

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

El algoritmo consta principalmente de cálculos MCD polinómicos y exponenciales . Fue inventado por David G. Cantor y Hans Zassenhaus en 1981. ^[1]

Podría decirse que es el algoritmo dominante para resolver el problema, ya que reemplazó al anterior algoritmo de Berlekamp de 1967. Actualmente se implementa en muchos sistemas de álgebra informática .

Descripción general

Fondo

El algoritmo de Cantor-Zassenhaus toma como entrada un polinomio sin cuadrados (es decir, uno sin factores repetidos) de grado n con coeficientes en un campo finito cuyos factores polinomiales irreducibles son todos de igual grado (existen algoritmos para factorizar eficientemente polinomios arbitrarios en un producto de polinomios que satisfacen estas condiciones, por ejemplo, es un polinomio sin cuadrados con los mismos factores que , de modo que el algoritmo de Cantor-Zassenhaus puede usarse para factorizar polinomios arbitrarios). Da como resultado un polinomio con coeficientes en el mismo campo tal que divide . Luego, el algoritmo se puede aplicar recursivamente a estos y a los divisores posteriores, hasta que encontremos la descomposición en potencias de polinomios irreducibles (recordando que el anillo de polinomios sobre cualquier cuerpo es un dominio de factorización único ). ${\displaystyle f(x)}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle f(x)/\gcd(f(x),f'(x))}$ ${\displaystyle f(x)}$ ${\displaystyle g(x)}$ ${\displaystyle g(x)}$ ${\displaystyle f(x)}$ ${\displaystyle f(x)}$

Todos los factores posibles de están contenidos dentro del anillo de factores . Si suponemos que tiene factores irreducibles , todos de grado d , entonces este anillo de factores es isomorfo al producto directo de anillos de factores . El isomorfismo de R a S , digamos , asigna un polinomio a la s -tupla de sus reducciones módulo de cada uno de los , es decir, si: ${\displaystyle f(x)}$ ${\displaystyle R={\frac {\mathbb {F} _{q}[x]}{\langle f(x)\rangle }}}$ ${\displaystyle f(x)}$ ${\displaystyle p_{1}(x),p_{2}(x),\ldots ,p_{s}(x)}$ ${\displaystyle S=\prod _{i=1}^{s}{\frac {\mathbb {F} _{q}[x]}{\langle p_{i}(x)\rangle }}}$ ${\displaystyle \phi }$ ${\displaystyle g(x)\in R}$ ${\displaystyle p_{i}(x)}$

${\displaystyle {\begin{aligned}g(x)&{}\equiv g_{1}(x){\pmod {p_{1}(x)}},\\g(x)&{}\equiv g_{2}(x){\pmod {p_{2}(x)}},\\&{}\ \ \vdots \\g(x)&{}\equiv g_{s}(x){\pmod {p_{s}(x)}},\end{aligned}}}$

entonces . Es importante tener en cuenta lo siguiente en este punto, ya que será de importancia crítica más adelante en el algoritmo: dado que cada uno de ellos es irreducible, cada uno de los anillos de factores en esta suma directa es de hecho un campo. Cada uno de estos campos tiene un título . ${\displaystyle \phi (g(x)+\langle f(x)\rangle )=(g_{1}(x)+\langle p_{1}(x)\rangle ,\ldots ,g_{s}(x)+\langle p_{s}(x)\rangle )}$ ${\displaystyle p_{i}(x)}$ ${\displaystyle q^{d}}$

Resultado principal

El resultado principal que subyace al algoritmo de Cantor-Zassenhaus es el siguiente: Si es un polinomio que satisface: ${\displaystyle a(x)\in R}$

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

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

¿Dónde está la reducción del módulo como antes y si dos de los tres conjuntos siguientes no están vacíos? ${\displaystyle a_{i}(x)}$ ${\displaystyle a(x)}$ ${\displaystyle p_{i}(x)}$

${\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 de : ${\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).}$

Algoritmo

El algoritmo de Cantor-Zassenhaus calcula polinomios del mismo tipo que el anterior utilizando el isomorfismo analizado en la sección Antecedentes. Procede de la siguiente manera, en el caso en que el campo sea de característica impar (el proceso se puede generalizar a 2 campos característicos de una manera bastante sencilla. ^[2] Seleccione un polinomio aleatorio tal que . Establezca y calcule . Dado que es un isomorfismo , tenemos (usando nuestra notación ahora establecida): ${\displaystyle a(x)}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle b(x)\in R}$ ${\displaystyle b(x)\neq 0,\pm 1}$ ${\displaystyle m=(q^{d}-1)/2}$ ${\displaystyle b(x)^{m}}$ ${\displaystyle \phi }$

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

Ahora bien, cada uno es un elemento de un campo de orden , como se señaló anteriormente. El subgrupo multiplicativo de este campo tiene orden y, por tanto, a menos que tengamos para cada i y, por tanto, para cada i . Si , entonces claro . Por tanto, es un polinomio del mismo tipo que el anterior. Además, dado que , al menos dos de los conjuntos y C no están vacíos, al calcular los MCD anteriores podemos obtener factores no triviales. Dado que el anillo de polinomios sobre un campo es un dominio euclidiano , podemos calcular estos MCD utilizando el algoritmo euclidiano . ${\displaystyle b_{i}(x)+\langle p_{i}(x)\rangle }$ ${\displaystyle q^{d}}$ ${\displaystyle q^{d}-1}$ ${\displaystyle b_{i}(x)=0}$ ${\displaystyle b_{i}(x)^{q^{d}-1}=1}$ ${\displaystyle b_{i}(x)^{m}=\pm 1}$ ${\displaystyle b_{i}(x)=0}$ ${\displaystyle b_{i}(x)^{m}=0}$ ${\displaystyle b(x)^{m}}$ ${\displaystyle a(x)}$ ${\displaystyle b(x)\neq 0,\pm 1}$ ${\displaystyle A,B}$

Aplicaciones

Una aplicación importante del algoritmo de Cantor-Zassenhaus es el cálculo de logaritmos discretos sobre campos finitos de orden de potencias primarias. Calcular logaritmos discretos es un problema importante en la criptografía de clave pública . Para un campo de orden de potencia prima, el método más rápido conocido es el método de cálculo de índices , que implica la factorización de elementos del campo. Si representamos el campo de orden de potencias primarias de la manera habitual, es decir, como polinomios sobre el campo base de orden primo, módulo reducido, un polinomio irreducible de grado apropiado, entonces esto es simplemente una factorización polinomial, como lo proporciona el algoritmo de Cantor-Zassenhaus. .

Implementación en sistemas de álgebra informática.

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

Ver también

• Factorización polinomial
• Factorización de polinomios sobre cuerpos finitos

Referencias

1. Cantor, David G .; Zassenhaus, Hans (abril de 1981), "Un nuevo algoritmo para factorizar polinomios sobre campos finitos", Matemáticas de la Computación , 36 (154): 587–592, doi : 10.1090/S0025-5718-1981-0606517-5 , JSTOR  2007663, Señor  0606517
2. Elia, Michele; Schipani, Davide (2015), "Mejoras en el algoritmo de factorización de Cantor-Zassenhaus", Mathematica Bohemica , 140 (3), Instituto de Matemáticas, Academia Checa de Ciencias: 271–290, arXiv : 1012.5322 , doi :10.21136/mb.2015.144395

Enlaces externos

• https://web.archive.org/web/20200301213349/http://blog.fkraiem.org/2013/12/01/polynomial-factorisation-over-finite-fields-part-3-final-splitting-cantor- zassenhaus-en-característica-impar/