Factorización de polinomios en un campo finito

La calculadora encuentra los factores de un polinomio mediante el algoritmo de Cantor-Zassenhaus

Esta página existe gracias a los esfuerzos de las siguientes personas:

Anton

Juan Manuel Gimenez

Juan Manuel Gimenez

Creado: 2021-05-26 22:55:31, Última actualización: 2021-05-26 22:55:31

Esta calculadora encuentra factores irreducibles de un polinomio univariante en el campo finito utilizando el algoritmo de Cantor-Zassenhaus. Inicialmente, realiza la factorización de grado distinto para encontrar los factores, que pueden descomponerse aún más. Finalmente, si es necesario, aplica un algoritmo de factorización de igual grado descrito justo debajo de la calculadora.

PLANETCALC, Factorización polinómica de Cantor-Zassenhaus en campo finito

Factorización polinómica de Cantor-Zassenhaus en campo finito

Polinomio de entrada
 
Solución
 
El archivo es muy grande; La ralentización del navegador puede ocurrir durante la carga y creación.
El archivo es muy grande; La ralentización del navegador puede ocurrir durante la carga y creación.

Algoritmo de factorización de Cantor-Zassenhaus

Este algoritmo tiene generalmente mejores características para módulos grandes que el similar algoritmo de factorización de Berlecamp.

  • Comprueba que el polinomio sea sin radicales
  • Encuentra todos los factores para grados distintos
  • Aplica el algoritmo de descomposición de igual grado, descrito a continuación, para cada factor cuyo grado sea mayor que el grado distinto obtenido en el paso anterior

Algoritmo de factorización de igual grado

// u(x) - Polinomio de entrada de grado rd  
//    que tiene r factores cada uno 
//    de grado d en el campo Fp
// p - orden del campo impar
// d - grado de los factores objetivo
// r - número de factores objetivo
s⟵ { u }
bucle mientras el tamaño(s) sea menor que r
        h ⟵ polinomio aleatorio  
                  de grado inferior a 2d
        g ⟵ h^(p^d-1/2) -1 mod u
        para cada a en s do 
              if deg(a) es mayor que d 
                    y gcd(g, a) ≠ 1 
                    y gcd(g, a) ≠ a entonces
                       eliminar a de s
                       añadir gcd(g,a) a s
                       añadir a/gcd(g,a) a s
              finalizar if
         finalizar do
finalizar bucle
salida s
URL copiada al portapapeles
PLANETCALC, Factorización de polinomios en un campo finito

Comentarios