En matemáticas y cálculo simbólico la factorización de un polinomio consiste en descomponerlo en un producto de factores irreducibles. 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. En la práctica, los algoritmos se han diseñado solo para polinomios con coeficientes en un cuerpo finito, en los números racionales o en una extensión de cuerpos de uno de ellos.
Todos los algoritmos de factorización, incluido el caso de los polinomios con múltiples variables sobre los números racionales, reducen el problema a este caso; véase factorización de polinomios. También se utiliza para diversas aplicaciones de cuerpos finitos, como la teoría de códigos (códigos de verificación de redundancia cíclica y el código BCH), criptografía (criptografía asimétrica mediante curvas elípticas) y teoría de números computacional.
Como la reducción de la factorización de polinomios a la de polinomios de una variable no tiene especificidad en el caso de coeficientes en un cuerpo finito, en este artículo solo se consideran polinomios con una variable.
Antecedentes
Cuerpo finito
La teoría de cuerpos finitos, cuyos orígenes se remontan a los trabajos de Carl Friedrich Gauss y Évariste Galois, ha jugado un importante papel en varias ramas de las matemáticas. 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. Las aplicaciones de cuerpos finitos introducen algunos de estos desarrollos en criptografía, cálculo simbólico y teoría de códigos.
Un cuerpo de Galois o cuerpo finito es un cuerpo con un orden finito (número de elementos). El orden de un cuerpo finito es siempre un número primo o una potencia de un número primo. Para cada potencia prima q = pr, existe exactamente un cuerpo finito con q elementos, salvo isomorfismo. Este cuerpo se indica como GF(q) o F q. Si p es primo, GF(p) es la característica de orden p; es el cuerpo de las clases de residuos respecto al módulo p, y sus elementos p se denotan 0, 1, ..., p-1. Así, a = b en GF(p) significa lo mismo que a ≡ b (mod p).
Polinomios irreducibles Sea F un cuerpo finito. En cuanto a los cuerpos generales, se dice que un polinomio no constante f en F[x] es irreducible sobre F si no es el producto de dos polinomios de grado positivo. 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. De hecho, para una potencia primaria q, sea Fq el cuerpo finito con q elementos, únicos salvo por isomorfismos. Un polinomio f de grado n mayor que uno, que es irreducible sobre Fq, define una extensión de cuerpo de grado n que es isomorfo al cuerpo con qn elementos, que son los polinomios de grado inferior a n; la suma, resta y multiplicación por un elemento de Fq son los de los polinomios; el producto de dos elementos es el resto de la división por f de su producto como polinomios; el inverso de un elemento puede calcularse mediante el algoritmo MCD extendido (véase aritmética de extensiones algebraicas).
De ello se deduce que, para calcular en un cuerpo finito de orden no primo, es necesario generar un polinomio irreducible. Para ello, el método común es tomar un polinomio al azar y probar su irreducibilidad. En aras de la eficiencia de la multiplicación en el cuerpo, es habitual buscar polinomios de la forma xn + ax + b.
Los polinomios irreducibles sobre cuerpos finitos también son útiles para los generadores de números pseudoaleatorios que utilizan registros de desplazamiento de retroalimentación y logaritmos discretos sobre F2n.
El número de polinomios mónicos irreducibles de grado n sobre Fq es el número de collares aperiódicos, dado por la función de conteo de collares de Moreau Mq(n). 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.Christophe Reutenauer, Mots circulaires et polynomes irreductibles, Ann. Sci. math Quebec, vol 12, no 2, pp. 275-285
Ejemplo El polinomio P = x4 + 1 es irreducible sobre Q pero no sobre ningún cuerpo finito.
En cualquier extensión de cuerpo de F2, P = (x + 1)4. En todos los demás cuerpos finitos, al menos uno de −1, 2 y −2 es un cuadrado, porque el producto de dos no cuadrados es un cuadrado, por lo que se tiene que Si entonces Si entonces Si entonces
Complejidad 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. Se puede realizar una división euclídea (división con resto) en períodos de tiempo similares. 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.
En los algoritmos que siguen, las complejidades se expresan en términos de número de operaciones aritméticas en Fq, utilizando algoritmos clásicos para la aritmética de polinomios.
Algoritmos de factorización Muchos algoritmos para factorizar polinomios sobre cuerpos finitos incluyen las siguientes tres etapas: Factorización libre de cuadrados Factorización en grados distintos Factorización de igual grado Una excepción importante es el algoritmo de Berlekamp, que combina las etapas 2 y 3.
Algoritmo de Berlekamp
El algoritmo de Berlekamp es históricamente importante por ser el primer algoritmo de factorización, que funciona bien en la práctica. Sin embargo, contiene un bucle en los elementos del cuerpo subyacente, lo que implica que es practicable solo en pequeños cuerpos finitos. Para un cuerpo subyacente fijo, su complejidad temporal es polinomial, pero, para cuerpos subyacentes generales, la complejidad es exponencial según el tamaño del cuerpo.
Factorización libre de cuadrados 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 determina primero la derivada y luego calcula el mcd del polinomio y su derivada. Si no es uno, el mcd vuelve a dividir el polinomio original, siempre que la derivada no sea cero (un caso que existe para polinomios no constantes definidos sobre cuerpos finitos).
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.
Este algoritmo funciona también sobre un cuerpo de característica cero, con la única diferencia de que nunca entra en los bloques de instrucciones donde se calculan las p raíces. Sin embargo, en este caso, el algoritmo de Yun es mucho más eficiente porque calcula los máximos divisores comunes de polinomios de grados inferiores. Una consecuencia es que, al factorizar un polinomio sobre los enteros, no se utiliza el algoritmo que sigue: primero se calcula la factorización libre de cuadrados sobre los enteros, y para factorizar los polinomios resultantes, se elige un p tal que permanecen libres de cuadrados de módulo p.
Algoritmo: SFF (Factorización sin cuadrados) Entrada: Un polinomio mónico f en Fq [x] donde q = pm Salida: Factorización libre de cuadrados de f R ← 1
# Hacer que w sea el producto (sin multiplicidad) de todos los factores de f que tienen # multiplicidad no divisible por p c ← mcd (f, f′) w ← f/c
# Paso 1: Identificar todos los factores en w i ← 1 mientrasw ≠ 1 hacer y ← mcd (w, c) fac ← w/y R ← R · faci w ← y; c ← c/y; i ← i + 1 terminar mientras # c es ahora el producto (con multiplicidad) de los factores restantes de f
# Paso 2: identificar todos los factores restantes mediante recursividad # Téngase en cuenta que estos son los factores de f que tienen multiplicidad divisible por p si c ≠ 1 entonces c ← c1/p R ← R · SFF (c)p terminar si
Salida (R)
La idea es identificar el producto de todos los factores irreducibles de f con la misma multiplicidad. Esto se hace en dos pasos. 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. Como todos los factores restantes tienen multiplicidad divisible por p, lo que significa que son potencias de p, simplemente se puede tomar la raíz cuadrada de p y aplicar la recursividad.
Ejemplo de factorización libre de cuadrados Sea
que se desea factorizar sobre el cuerpo con tres elementos.
El algoritmo calcula primero
Dado que la derivada no es cero, se tiene que y se entra en el ciclo mientras. Después de un bucle se tiene que , y con actualizaciones , y . La segunda vez a través del ciclo resulta , , , con actualizaciones , y . La tercera vez a través del bucle tampoco cambia . Pasando por cuarta vez a través del bucle se obtiene , , , con actualizaciones , y . Dado que w = 1, se sale del bucle mientras. 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
Factorización de grados distintos 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.
Algoritmo Factorización de grados distintos (DDF) Entrada: Un polinomio mónico libre de cuadrados Salida: El conjunto de todos los pares , tales que tiene un factor irreducible de grado y es el producto de todos los factores mónicos irreducibles de de grado . Empezar
mientras hacer
si , entonces
terminar si
fin mientras; si , entonces ; si , entonces devuelve , si no devuelve Final
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. Sin embargo
puede ser reemplazado por
Por lo tanto, se tiene que calcular:
hay dos métodos:
Factorización de igual grado
Algoritmo de Cantor-Zassenhaus
En esta sección, se considera la factorización de un polinomio mónico de una variante libre de cuadrados f, de grado n, sobre un cuerpo finito Fq, que tiene r ≥ 2 factores irreducibles distintos por pares cada uno de grado d.