Factorización de polinomios

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. Factorización polinómica es una de las herramientas fundamentales de los sistemas de álgebra computacional. Ejemplo La historia de la factorización polinómica comienza con Hermann Schubert quien en 1793 describió el primer algoritmo de factorización de polinomios, y Leopold Kronecker, quien redescubrió el algoritmo de Schubert en 1882 y la amplió a polinomios multivariados y con coeficientes en una extensión algebraica. 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.

Formulación

Anillos de polinomios sobre los enteros o sobre un campo son dominios de factorización única. Esto significa que cada elemento de estos anillos es el producto de una constante y el producto de polinomios irreducibles (aquellos que no son el producto de dos polinomios no constantes). Por otra parte, esta descomposición es única hasta la multiplicación de los factores por constantes invertibles.

La factorización depende del campo base. 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:

• Factorización sin radicales
• Factorización sobre campos finitos

y reducciones:

• Desde el caso multivariado al univariado.
• Desde coeficientes en una extensión puramente trascendental al caso multivariado sobre el campo base (véase más abajo)
• Desde coeficientes en una extensión algebraica a coeficientes en el campo base
• Desde coeficientes racionales a coeficientes enteros (véase más abajo)
• Desde coeficientes enteros a coeficientes en un campo primo con p elementos, para cierto p.

Factorización primitiva basada en contenido

Véase también: Lema de Gauss

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. La parte primitiva de p es primpart(p)=p/cont(p), que es un polinomio primitivo con coeficientes enteros. Esto define una factorización de p como el producto de un número entero y un polinomio primitivo. Esta factorización es única hasta el signo del contenido. Es usual elegir el signo del contenido tal que el coeficiente principal de la parte primitiva sea positivo.

Por ejemplo,

${\displaystyle -10x^{2}+5x+5=(-5)\cdot (2x^{2}-x-1)\,}$ 

es una factorización en el contenido y la parte primitiva.

Cada polinomio Q con coeficientes racionales puede ser escrito como

${\displaystyle q={\frac {p}{c}},}$ 

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:

${\displaystyle {\text{cont}}(q)={\frac {{\text{cont}}(p)}{c}},}$ 

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. Esta factorización es también única hasta la elección del signo.

Por ejemplo,

${\displaystyle {\frac {1}{3}}x^{5}+{\frac {7}{2}}x^{2}+2x+1={\frac {1}{6}}(2x^{5}+21x^{2}+12x+6)}$ 

es una factorización en el contenido y la parte primitiva.

Gauss demostró en primer lugar que el producto de dos polinomios primitivos también es primitivo (Lema de Gauss). Esto implica que un polinomio primitivo es irreducible sobre los racionales si y sólo si es irreducible sobre los números 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. Por otro lado, la factorización sobre los números enteros de un polinomio con coeficientes enteros es el producto de la factorización de su parte primitiva por la factorización de su contenido.

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". Esto permite reducir la factorización sobre una extensión puramente trascendente de F a la factorización de polinomios multivariados sobre F.

Factorización sin radicales (Square-free factorization)

Si dos o más factores de un polinomio son idénticos entre sí, entonces el polinomio es un múltiplo de la raíz de este factor. En el caso de polinomios univariantes, esto resulta en raíces múltiples. En este caso, el factor múltiple es también un factor de las derivadas del polinomio (con respecto a cualquiera de las variables), que a su vez es un polinomio de menor grado. En el caso de los polinomios univariantes sobre los racionales (o en general, sobre un campo de característica cero), el algoritmo de Yun explota esta característica al factorizar eficientemente el polinomio en factores que no son múltiplos de una raíz, por lo que son llamados sin radicales (square-free). Para factorizar el polinomio inicial, basta con factorizar cada factor sin radicales. Por tanto, este algoritmo es el primer paso de casi todos los algoritmos de factorización de polinomios.

El algoritmo de Yun se extiende fácilmente al caso multivariado considerando un polinomio multivariante como un polinomio univariado sobre un anillo de polinomios.

En el caso de un polinomio sobre un campo finito, el algoritmo de Yun sólo se aplica si el grado es menor que la característica, porque, de lo contrario, la derivada de un polinomio distinto de cero puede ser cero (sobre el campo con p elementos, la derivada de una polinomio en x^p es siempre cero). Sin embargo, una sucesión de cálculos GCD, a partir del polinomio y su derivada, permite calcular la descomposición sin radicales.

La mayoría de los algoritmos de factorización, incluyendo los más eficientes, comienzan por una factorización sin radicales.

Métodos clásicos

Esta sección describe los métodos clásicos que resultan conveniente cuando se calcula a mano. Estos métodos no se utilizan para los cálculos por ordenador, ya que utilizan la factorización sobre enteros , que tiene una complejidad mucho mayor que la factorización polinómica.

Obteniendo factores lineales

Todos los factores lineales con coeficientes racionales se pueden encontrar utilizando el Teorema de la raíz racional. Si el polinomio a factorizar es ${\displaystyle a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{1}x+a_{0}}$ , entonces todos los posibles factores (lineales) son de la forma ${\displaystyle b_{1}x-b_{0}}$ , donde ${\displaystyle b_{1}}$  es un factor entero de ${\displaystyle a_{0}}$  y ${\displaystyle b_{0}}$  es un factor entero de ${\displaystyle a_{n}}$ . Todas las posibles combinaciones de factores enteros pueden ser verificadas, y cada combinación válida puede ser factorizada usando la división polinomial. Si el polinomio original es el producto de varios factores, de los cuales al menos dos tienen grado 2 o superior, esta técnica sólo proporciona una factorización parcial, de lo contrario la factorización es completa. 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.

Método de Kronecker

Dado que polinomios enteros deben factorizar en factores polinomiales enteros, y la evaluación de polinomios enteros a valores enteros deben producir números enteros, los valores enteros de un polinomio deben tenerse en cuenta sólo en número finito de formas, y producen sólo un número finito de posibles factores polinómicos.

Por ejemplo, considere

${\displaystyle f(x)=x^{5}+x^{4}+x^{2}+x+2}$ .

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. Usaremos ${\displaystyle f(0)=2}$ , ${\displaystyle f(1)=6}$  y ${\displaystyle f(-1)=2}$ . Tenga en cuenta que si alguno de estos valores es 0, entonces ya se ha encontrado una raíz (y por consiguiente un factor). Si ninguno es 0, entonces cada uno tiene una cantidad finita de divisores. Ahora, 2 sólo puede factorizarse como

1×2, 2×1, (−1)×(−2), o (−2)×(−1).

Por lo tanto, si existe un factor polinómico entero de segundo grado existe, debe tomar uno de los valores

1, 2, −1, ó −2

en ${\displaystyle x=0}$ , y asimismo en ${\displaystyle x=-1}$ . Hay ocho formas diferentes de Factor 6 (uno para cada divisor de 6), por lo que hay

4×4×8 = 128

combinaciones posibles, de las cuales la mitad se puede desechar como los negativos de la otra mitad, que corresponden a 64 posibles polinomios enteros de segundo grado que deben ser comprobados. Estos son los únicos posibles factores de polinomios enteros de ${\displaystyle f(x)}$ . Probándolos de forma exhaustiva se comprueba

${\displaystyle p(x)=x^{2}+x+1}$ 

construido a partir de ${\displaystyle p(0)=1}$ , ${\displaystyle p(1)=3}$  y ${\displaystyle p(-1)=1}$ , factorizando ${\displaystyle f(x)}$ .

Dividiendo ${\displaystyle f}$  por ${\displaystyle p}$  da el otro factor ${\displaystyle q(x)=x^{3}-x+2}$ , tal que ${\displaystyle f=pq}$ . Ahora se puede probar de forma recursiva para encontrar factores de ${\displaystyle p}$  y ${\displaystyle q}$ . Resulta que ambos son irreducible sobre los números enteros, de manera que la factorización irreductible de ${\displaystyle f}$  es

${\displaystyle f(x)=p(x)q(x)=(x^{2}+x+1)(x^{3}-x+2)}$ 

(Van der Waerden, Secciones 5.4 y 5.6)

Métodos modernos

Algoritmo LLL

Artículo principal: Algoritmo LLL

El primer algoritmo de complejidad temporal polinomial para factorizar polinomios racionales fue descubierto por Lenstra, Lenstra and Lovász. Usualmente llamado "para factorizar polinomios racionales LLL". (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.

Sin embargo el algoritmo LLL es utilizado por algoritmos de factorización más rápidos para generar una factorización modular para una factorización sobre los números enteros.

Método de Trager

Podemos factorizar un polinomio ${\displaystyle p(x)\in K[x]}$ , donde ${\displaystyle K}$  es una extensión de campo finita de ${\displaystyle \mathbb {Q} }$ . Primero, usando factorización sin radicales, podemos suponer que el polinomio no tiene radicales. A continuación escribimos ${\displaystyle L=K[x]/p(x)}$  explícitamente como un álgebra sobre ${\displaystyle \mathbb {Q} }$ . A continuación escogemos un elemento aleatorio ${\displaystyle \alpha \in L}$ . Por el teorema del elemento primitivo, ${\displaystyle \alpha }$  genera ${\displaystyle L}$  sobre ${\displaystyle \mathbb {Q} }$  con una alta probabilidad. Si este es el caso, podemos calcular el polinomio minimal, ${\displaystyle q(y)\in \mathbb {Q} [y]}$  de ${\displaystyle \alpha }$  sobre ${\displaystyle \mathbb {Q} }$ . Factorizando

${\displaystyle q(y)=\prod _{i=1}^{n}q_{i}(y)}$ 

sobre ${\displaystyle \mathbb {Q} [y]}$ , determinamos que

${\displaystyle L=\mathbb {Q} [\alpha ]=\mathbb {Q} [y]/q(y)=\prod _{i=1}^{n}\mathbb {Q} [y]/q_{i}(y)}$ 

(nótese que ${\displaystyle L}$  es un anillo reducido dado que ${\displaystyle p(x)}$  es libre de radicales), donde ${\displaystyle \alpha }$  corresponde al elemento ${\displaystyle (y,y,\ldots ,y)}$ . Tenga en cuenta que esta es la única descomposición de ${\displaystyle L}$  como un campo de productos. Por lo tanto esta descomposición es el mismo que

${\displaystyle \prod _{i=1}^{m}K[x]/p_{i}(x)}$ 

donde

${\displaystyle p(x)=\prod _{i=1}^{m}p_{i}(x)}$ 

es la factorización de ${\displaystyle p(x)}$  sobre ${\displaystyle K[x]}$ . Al escribir ${\displaystyle x\in L}$  y generadores de ${\displaystyle K}$  como polinomios en ${\displaystyle \alpha }$ , podemos determinar las incrustaciones de ${\displaystyle x}$  y ${\displaystyle K}$  en las componentes ${\displaystyle \mathbb {Q} [y]/q_{i}(y)=K[x]/p_{i}(x)}$ . Al encontrar el polinomio mínimo de ${\displaystyle x}$  en este anillo, hemos calculado ${\displaystyle p_{i}(x)}$ , y por lo tanto factorizar ${\displaystyle p(x)}$  sobre ${\displaystyle K.}$ 

Referencias

• Fröhlich, A.; Shepherson, J. C. (1955), «On the factorisation of polynomials in a finite number of steps», Mathematische Zeitschrift 62 (1), ISSN 0025-5874 .
• Trager, B.M., «Algebraic Factoring and Rational Function Integration», Proc. SYMSAC 76 http://dl.acm.org/citation.cfm?id=806338 .
• Bernard Beauzamy, Per Enflo, Paul Wang (octubre de 1995). «Quantitative Estimates for Polynomials in One or Several Variables: From Analysis and Number Theory to Symbolic and Massively Parallel Computation». Mathematics Magazine 67 (4): 243-257. JSTOR 2690843. doi:10.2307/2690843.  (accessible to readers with undergraduate mathematics)
• Cohen, Henri (1993). A course in computational algebraic number theory. Graduate Texts in Mathematics 138. Berlin, New York: Springer-Verlag. ISBN 978-3-540-55640-4. MR 1228206. 
• Kaltofen, Erich (1982), «Factorization of polynomials», en B. Buchberger; R. Loos; G. Collins, eds., Computer Algebra, Springer Verlag, consultado el 20 de septiembre de 2012 .
• Knuth, Donald E (1997). «4.6.2 Factorization of Polynomials». Seminumerical Algorithms. The Art of Computer Programming 2 (Third edición). Reading, Massachusetts: Addison-Wesley. pp. 439-461, 678-691. ISBN 0-201-89684-2. 
• Lenstra, A. K.; Lenstra, H. W.; Lovász, László (1982). «Factoring polynomials with rational coefficients». Mathematische Annalen 261 (4): 515-534. ISSN 0025-5831. MR 682664. doi:10.1007/BF01457454. 
• Van der Waerden, Algebra (1970), trans. Blum and Schulenberger, Frederick Ungar.

Lecturas adicionales

• Kaltofen, Erich (1990), «Polynomial Factorization 1982-1986», en D. V. Chudnovsky; R. D. Jenks, eds., Computers in Mathematics, Lecture Notes in Pure and Applied Mathematics 125, Marcel Dekker, Inc., consultado el 14 de octubre de 2012 .
• Kaltofen, Erich (1992), «Polynomial Factorization 1987–1991», Proceedings of Latin ’92, Springer Lect. Notes Comput. Sci. 583, Springer, consultado el 14 de octubre de 2012 .

•   Datos: Q392477