En matemáticas y álgebra computacional, la factorización de polinomios o factorización polinómica se refiere a factorizar un polinomio con coeficientes en un campo dado o en los números enteros en factores irreducibles con coeficientes en el mismo dominio.
Pero la mayor parte de los conocimientos sobre este tema no es mayor que alrededor del año 1965 y los primeros sistemas de álgebra computacional.
En una entrevista sobre el tema, Erich Kaltofen escribió en 1982 (véase la bibliografía): Cuando los algoritmos de pasos finitos largo tiempo conocidos se pusieron por primera vez en los ordenadores, resultaron ser altamente ineficiente.
El hecho de que casi cualquier polinomio uni o multivariado de hasta grado 100 y con coeficientes de tamaño moderado (hasta 100 bits) se puede factorizar mediante algoritmos modernos en unos pocos minutos indica el éxito con que este problema se ha atacado durante los últimos quince años.
Por otra parte, esta descomposición es única hasta la multiplicación de los factores por constantes invertibles.
Por ejemplo, el teorema fundamental del álgebra, que establece que todo polinomio con coeficientes complejos tiene raíces complejas, implica que un polinomio con coeficientes enteros se puede factorizar (mediante algoritmos numéricos) en factores lineales sobre los números complejos.
Del mismo modo, sobre los números reales, los factores irreducibles tienen grado a lo sumo dos, mientras que hay polinomios de cualquier grado que son irreducible sobre los números racionales.
La factorización polinómica sólo tiene sentido para coeficientes en un campo computable en donde cada elemento puede ser representado en una computadora y existan algoritmos para las operaciones aritméticas.
Fröhlich y Shepherson han proporcionado ejemplos de estos campos para los que puede no existir ningún algoritmo de factorización.
Los campos de los coeficientes para los que se conocen algoritmos de factorización incluyen campos principales (es decir, los números racionales y la aritmética modular sobre primos) y sus extensiones de campo finito.
Coeficientes enteros también son manejables: el método de Kronecker sólo es interesante desde un punto de vista histórico, los algoritmos modernos provienen de una sucesión de: y reducciones: En esta sección, se muestra que la factorización sobre Q (los números racionales) y sobre Z (los enteros) es esencialmente el mismo problema.
El contenido de un polinomio p ∈ Z[X], denotado como "cont(p)", es, hasta su signo, el máximo común divisor de sus coeficientes.
Es usual elegir el signo del contenido tal que el coeficiente principal de la parte primitiva sea positivo.
Cada polinomio Q con coeficientes racionales puede ser escrito como donde p ∈ Z[X] y C ∈ Z: basta con tomar para C un múltiplo de todos los denominadores de los coeficientes de Q (por ejemplo, su producto) y p = cq.
El contenido de Q se define como: y la parte primitiva de q es la de p. En cuanto a los polinomios con coeficientes enteros, esto define una factorización en un número racional y un polinomio primitivo con coeficientes enteros.
Además implica que la factorización sobre los números racionales de un polinomio con coeficientes racionales es la misma que la factorización sobre los números enteros de su parte primitiva.
En otras palabras, integer GDD computation permite reducir la factorización de un polinomio sobre los números racionales a la factorización de un polinomio primitivo con coeficientes enteros, y reducir la factorización sobre los números enteros a la factorización de un número entero y un polinomio primitivo.
Todo lo anterior se sigue cumpliendo si Z es sustituido por un anillo de polinomios sobre un campo F y Q se sustituye por un campo de cocientes racionales sobre F en las mismas variables, con la única diferencia de que "hasta un signo" debe sustituirse por "hasta la multiplicación por una constante invertible en F".
En el caso de polinomios univariantes, esto resulta en raíces múltiples.
Sin embargo, una sucesión de cálculos GCD, a partir del polinomio y su derivada, permite calcular la descomposición sin radicales.
Esta sección describe los métodos clásicos que resultan conveniente cuando se calcula a mano.
, entonces todos los posibles factores (lineales) son de la forma
Tenga en cuenta que en el caso de un polinomio cúbico, si el cubo es factorizable, el Teorema de la raíz racional ya sea en un factor lineal y un factor cuadrático irreducible, o en tres factores lineales.
Por ejemplo, considere Si estos factores polinómicos están sobre Z, entonces al menos uno de ellos debe tener grado dos o inferior.
Se necesitan tres valores para encontrar un polinomio único de segundo grado.
Tenga en cuenta que si alguno de estos valores es 0, entonces ya se ha encontrado una raíz (y por consiguiente un factor).
Ahora, 2 sólo puede factorizarse como Por lo tanto, si existe un factor polinómico entero de segundo grado, debe tomar uno de los valores en
es (Van der Waerden, Secciones 5.4 y 5.6) El primer algoritmo de complejidad temporal polinomial para factorizar polinomios racionales fue descubierto por Lenstra, Lenstra and Lovász.
(Lenstra, Lenstra y Lovász, 1982) A pesar de que, teóricamente, es más rápido en caso peor, el algoritmo no es eficiente en la práctica.
«Quantitative Estimates for Polynomials in One or Several Variables: From Analysis and Number Theory to Symbolic and Massively Parallel Computation».