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
|
Este contenido está bajo licencia de Creative Commons Attribution/Share-Alike License 3.0 (Unported). Esto significa que puedes redistribuirlo o modificar su contenido en forma libre bajo las mismas condiciones de licencia y debes mantener la atribución del mismo al autor original de este trabajo colocando un hipervínculo en tu sitio web a este trabajo https://es.planetcalc.com/8372/. Así mismo, por favor no modifiques o alteres ninguna de las referencias al trabajo original (si hubiera alguna) que se encuentre en este contenido.
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.
Factorización polinómica de Cantor-Zassenhaus en campo finito
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
Comentarios