Esta descomposición es teóricamente posible y es única para polinomios con coeficientes en cualquier cuerpo, pero se necesitan restricciones bastante fuertes en el cuerpo de los coeficientes para permitir el cálculo de la factorización mediante un algoritmo.
Debido a la aplicabilidad del concepto en otros temas de matemáticas y ciencias como la informática, ha habido un resurgimiento del interés en los cuerpos finitos, lo que se debe en parte a importantes aplicaciones en teoría de códigos y criptografía.
Un polinomio de grado positivo que no es irreducible sobre F se llama reducible sobre F. Los polinomios irreducibles permiten construir los cuerpos finitos de orden no primo.
Para ello, el método común es tomar un polinomio al azar y probar su irreducibilidad.
La función de collar estrechamente relacionada Nq(n) cuenta los polinomios mónicos de grado n que son primarios (una potencia de un irreducible); o, alternativamente, polinomios irreducibles de todos los grados d que dividen a n.[1] El polinomio P = x4 + 1 es irreducible sobre Q pero no sobre ningún cuerpo finito.
Los algoritmos de factorización polinomial utilizan operaciones polinomiales básicas como productos, divisiones, máximo común divisor (mcd), potencias de un polinomio con otro módulo, etc. Una multiplicación de dos polinomios de grado n como máximo se puede realizar en operaciones O(n2) en Fq usando aritmética clásica, o en O con las operaciones (nlog(n) log (log (n))) en Fq usando aritmética rápida.
La dificultad de obtener un máximo común divisor polinómico entre dos polinomios de grado como máximo n se puede tomar como operaciones O(n2) en Fq usando métodos clásicos, o como O(nlog2(n) log(log(n))) operaciones en Fq usando métodos rápidos.
Para dos polinomios h y g de grado como máximo n, la exponenciación hq mod g se puede hacer con O(log(q)) productos polinómicos, usando el método de exponenciación binaria, es decir O(n2log(q)) operaciones en Fq usando métodos clásicos, o O(nlog(q) log(n) log(log (n))) operaciones en Fq usando métodos rápidos.
Muchos algoritmos para factorizar polinomios sobre cuerpos finitos incluyen las siguientes tres etapas: Una excepción importante es el algoritmo de Berlekamp, que combina las etapas 2 y 3.
El algoritmo determina una factorización libre de cuadrados para polinomios cuyos coeficientes provienen del cuerpo finito Fq de orden q = pm con p primo.
Este algoritmo utiliza el hecho de que, si la derivada de un polinomio es cero, entonces es un polinomio en xp, que es, si los coeficientes pertenecen a Fp, la p potencia del polinomio obtenido al sustituir x por x1/p.
Si los coeficientes no pertenecen a Fp, la raíz p-ésima de un polinomio con derivada cero se obtiene mediante la misma sustitución en x, completada aplicando el inverso del automorfismo de Frobenius a los coeficientes.
El primer paso usa la derivada formal de f para encontrar todos los factores con multiplicidad no divisible por p. El segundo paso identifica los factores restantes.
Sea que se desea factorizar sobre el cuerpo con tres elementos.
La tercera vez a través del bucle tampoco cambia R. Pasando por cuarta vez a través del bucle se obtiene y = 1, z = x + 2, R = (x + 1)(x + 2)4, con actualizaciones i = 5, w = 1 y c = x6 + 1.
Dado que c ≠ 1, debe ser un cubo perfecto, la raíz cúbica de c, obtenida al reemplazar x3 por x es x2 + 1, y llamar al procedimiento sin cuadrados determina de forma recursiva que el resultado está libre de cuadrados.
Por lo tanto, dividirlo en un cubo y combinarlo con el valor de R hasta ese punto da la descomposición sin cuadrados Este algoritmo divide un polinomio libre de cuadrados en un producto de polinomios cuyos factores irreducibles tienen todos el mismo grado.
Sea f ∈ Fq[x] de grado n el polinomio a factorizar.
La corrección del algoritmo se basa en lo siguiente: A primera vista, este procedimiento no es eficiente, ya que implica calcular el MCD de polinomios de un grado que es exponencial con el grado del polinomio de entrada.
Luego, en cada iteración del ciclo, se calcula el producto de una matriz por un vector (con O(deg(f)2 operaciones).
cada uno de grado d. Primero se describe un algoritmo de Cantor y Zassenhaus (1981) y luego una variante que tiene una complejidad ligeramente mejor.
Todos estos algoritmos requieren un orden impar q del cuerpo de coeficientes.
Cabe señalar que este algoritmo también funciona si los factores no tienen el mismo grado (en este caso, el número "r" de factores, necesario para detener el ciclo mientras, se encuentra como la dimensión del núcleo).
Sin embargo, la complejidad es ligeramente mejor si se realiza la factorización sin cuadrados antes de usar este algoritmo (dado que n puede disminuir con la factorización sin cuadrados, esto reduce la complejidad de los pasos críticos).
Sin embargo, es menos eficiente, en la práctica, que los algoritmos de la sección anterior.
Sea g = g1 ... gk la factorización deseada, donde gi son polinomios mónicos irreducibles distintos de grado d. Sea n = deg(g) = kd.
Como se describió en secciones anteriores, para la factorización sobre cuerpos finitos, existen algoritmos probabilistas (por ejemplo, el algoritmo de Cantor-Zassenhaus), lo que condiciona su complejidad temporal.
Sean p1, ..., pk, todos los divisores primos de n, y sea
De hecho, si f tiene un factor de grado que no divide a n, entonces f no divide a
más pequeño mediante cuadratura repetida o usando el automorfismo de Frobenius, y luego tomar el mcd correspondiente.