Factorización de polinomios - Factorization of polynomials

En matemáticas y álgebra informática , la factorización de polinomios o la factorización de polinomios expresa un polinomio con coeficientes en un campo dado o en los números enteros como el producto de factores irreducibles con coeficientes en el mismo dominio. La factorización polinomial es uno de los componentes fundamentales de los sistemas de álgebra computarizada .

El primer algoritmo de factorización de polinomios fue publicado por Theodor von Schubert en 1793. Leopold Kronecker redescubrió el algoritmo de Schubert en 1882 y lo extendió a polinomios multivariados y coeficientes en una extensión algebraica. Pero la mayor parte del conocimiento sobre este tema no es anterior a alrededor de 1965 y los primeros sistemas de álgebra computarizada :

Cuando los algoritmos de pasos finitos, conocidos desde hace mucho tiempo, se instalaron por primera vez en las computadoras, resultaron ser muy ineficientes. El hecho de que casi cualquier polinomio univariante o multivariado de grado hasta 100 y con coeficientes de un tamaño moderado (hasta 100 bits) pueda ser factorizado por algoritmos modernos en unos pocos minutos de tiempo de computadora indica cuán exitosamente se ha atacado este problema durante los últimos quince años. (Erich Kaltofen, 1982)

Hoy en día, los algoritmos y las computadoras modernos pueden factorizar rápidamente polinomios univariados de grado superior a 1000 que tienen coeficientes con miles de dígitos.

Formulación de la pregunta

Los anillos polinomiales sobre los números enteros o sobre un campo son dominios de factorización únicos . Esto significa que cada elemento de estos anillos es un producto de una constante y un producto de polinomios irreducibles (aquellos que no son el producto de dos polinomios no constantes). Además, 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 cada polinomio con complejos coeficientes tiene raíces complejas, implica que un polinomio con coeficientes enteros se puede factorizar (con algoritmos de búsqueda de raíz ) en factores lineales sobre el campo complejo C . Del mismo modo, el campo de reales , los factores irreducibles tienen un grado a lo sumo dos, mientras que hay polinomios de cualquier grado que son irreducible sobre el campo de los números racionales Q .

La cuestión de la factorización de polinomios sólo tiene sentido para los coeficientes de un campo computable cuyos elementos pueden representarse en una computadora y para los que existen algoritmos para las operaciones aritméticas. Sin embargo, esta no es una condición suficiente: Fröhlich y Shepherdson dan ejemplos de tales campos para los que no puede existir un algoritmo de factorización.

Los campos de coeficientes para los que se conocen algoritmos de factorización incluyen campos primos (es decir, el campo de los racionales y la aritmética modular primaria ) y sus extensiones de campo generadas finitamente . Los coeficientes enteros también son manejables. El método clásico de Kronecker es interesante sólo desde un punto de vista histórico; Los algoritmos modernos proceden de una sucesión de:

• Factorización libre de cuadrados
• Factorización sobre campos finitos

y reducciones:

• Del caso multivariado al caso univariado .
• Desde coeficientes en una extensión puramente trascendental hasta el caso multivariado sobre el campo de tierra (ver más abajo ).
• Desde coeficientes en una extensión algebraica hasta coeficientes en el campo de tierra (ver más abajo ).
• De coeficientes racionales a coeficientes enteros (ver más abajo ).
• Desde coeficientes enteros hasta coeficientes en un campo primo con p elementos, para una p bien elegida (ver más abajo ).

Factorización primitiva de contenido parcial

En esta sección, mostramos que factorizar 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 "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 en el producto de un número entero y un polinomio primitivo. Esta factorización es única hasta el signo del contenido. Es una convención habitual elegir el signo del contenido de manera que el coeficiente principal de la parte primitiva sea positivo.

Por ejemplo,

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

es una factorización en contenido y parte primitiva.

Todo polinomio q con coeficientes racionales puede escribirse

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

donde p ∈ Z [ X ] yc ∈ Z : basta 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 también es única hasta la elección de un signo.

Por ejemplo,

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

es una factorización en contenido y parte primitiva.

Gauss demostró que el producto de dos polinomios primitivos también es primitivo ( lema de Gauss ). Esto implica que un polinomio primitivo es irreductible sobre los racionales si y solo si es irreductible sobre los enteros. Esto implica también que la factorización sobre los racionales de un polinomio con coeficientes racionales es la misma que la factorización sobre los números enteros de su parte primitiva. Del mismo modo, 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, un cálculo MCD de enteros reduce la factorización de un polinomio sobre los racionales a la factorización de un polinomio primitivo con coeficientes enteros, y la factorización sobre los enteros a la factorización de un polinomio entero y primitivo.

Todo lo que precede permanece verdadero si Z se reemplaza por un anillo polinomial sobre un campo F y Q se reemplaza por un campo de funciones racionales sobre F en las mismas variables, con la única diferencia de que "hasta un signo" debe ser reemplazado por " hasta la multiplicación por una constante invertible en F ". Esto reduce la factorización sobre un puramente trascendental extensión campo de la F a la factorización de polinomios multivariados más de F .

Factorización libre de cuadrados

Si dos o más factores de un polinomio son idénticos, entonces el polinomio es un múltiplo del cuadrado de este factor. El factor múltiple también es un factor de la derivada del polinomio (con respecto a cualquiera de las variables, si son varias).

Para polinomios univariados, múltiples factores son equivalentes a múltiples raíces (sobre un campo de extensión adecuado). Para polinomios univariados sobre los racionales (o más generalmente sobre un campo de característica cero), el algoritmo de Yun explota esto para factorizar eficientemente el polinomio en factores libres de cuadrados, es decir, factores que no son múltiplos de un cuadrado, realizando una secuencia de Cálculos de GCD que comienzan con mcd ( f ( x ), f '( x )). Para factorizar el polinomio inicial, basta factorizar cada factor libre de cuadrados. La factorización libre de cuadrados es, por tanto, el primer paso en la mayoría de los algoritmos de factorización polinomial.

El algoritmo de Yun extiende esto al caso multivariado al considerar un polinomio multivariado como un polinomio univariado sobre un anillo polinomial.

En el caso de un polinomio sobre un campo finito, el algoritmo de Yun se aplica solo 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 un polinomio en x ^p es siempre cero). No obstante, una sucesión de cálculos de GCD, a partir del polinomio y su derivada, permite calcular la descomposición sin cuadrados; ver Factorización polinomial sobre campos finitos # Factorización sin cuadrados .

Métodos clásicos

En esta sección se describen métodos de libros de texto que pueden resultar convenientes al calcular a mano. Estos métodos no se utilizan para cálculos informáticos porque utilizan la factorización de enteros , que actualmente es más lenta que la factorización de polinomios.

Obtención de factores lineales

Todos los factores lineales con coeficientes racionales se pueden encontrar utilizando la prueba de la raíz racional . Si el polinomio que se va a factorizar es , entonces todos los factores lineales posibles tienen la forma , donde es un factor entero de y es un factor entero de . Se puede probar la validez de todas las combinaciones posibles de factores enteros, y cada uno válido se puede factorizar utilizando la división polinomial larga . Si el polinomio original es el producto de factores al menos dos de los cuales son de grado 2 o superior, esta técnica solo proporciona una factorización parcial; de lo contrario, la factorización está completa. En particular, si hay exactamente un factor no lineal, será el polinomio que quede después de que se hayan factorizado todos los factores lineales. En el caso de un polinomio cúbico , si el cúbico es factorizable, la prueba de la raíz racional da una factorización completa, ya sea en un factor lineal y un factor cuadrático irreducible, o en tres factores lineales. ${\ Displaystyle a_ {n} x ^ {n} + a_ {n-1} x ^ {n-1} + \ cdots + a_ {1} x + a_ {0}}$${\ Displaystyle b_ {1} x-b_ {0}}$${\ Displaystyle b_ {1}}$${\ Displaystyle a_ {n}}$${\ Displaystyle b_ {0}}$${\ Displaystyle a_ {0}}$

El método de Kronecker

Dado que los polinomios enteros deben factorizarse en factores polinomiales enteros, y la evaluación de polinomios enteros con valores enteros debe producir números enteros, los valores enteros de un polinomio se pueden factorizar solo en un número finito de formas y producir solo un número finito de posibles factores polinomiales.

Por ejemplo, considere

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

Si este polinomio factoriza sobre Z , entonces al menos uno de sus factores debe ser de grado dos o menos, por lo que está determinado de forma única por tres valores . Por lo tanto, calculamos tres valores , y . Si uno de estos valores es 0, tenemos un factor lineal. Si los valores son distintos de cero, podemos enumerar las posibles factorizaciones para cada uno. Ahora, 2 solo se puede factorizar como ${\ Displaystyle p (x)}$${\ Displaystyle p (x)}$${\ Displaystyle f (0) = 2}$${\ Displaystyle f (1) = 6}$${\ Displaystyle f (-1) = 2}$

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

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

p (0) = 1, 2, −1 o −2

e igualmente para p (1). Hay ocho factorizaciones de 6 (cuatro cada una para 1 × 6 y 2 × 3), lo que hace un total de 4 × 4 × 8 = 128 triples posibles ( p (0), p (1), p (−1)), de los cuales la mitad se puede descartar como negativos de la otra mitad. Por lo tanto, debemos verificar 64 polinomios enteros explícitos como posibles factores de . Probarlos exhaustivamente revela que ${\ Displaystyle p (x) = ax ^ {2} + bx + c}$${\ Displaystyle f (x)}$

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

construido a partir de ( g (0), g (1), g (−1)) = (1,3,1) factores . ${\ Displaystyle f (x)}$

Dividir f ( x ) por p ( x ) da el otro factor , de modo que . Ahora uno puede probar recursivamente para encontrar factores de p ( x ) yq ( x ), en este caso usando la prueba de la raíz racional. Resulta que ambos son irreductibles, por lo que la factorización irreducible de f ( x ) es: ${\ Displaystyle q (x) = x ^ {3} -x + 2}$${\ Displaystyle f (x) = p (x) q (x)}$

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

Métodos modernos

Factorizar sobre campos finitos

Factorizar polinomios univariados sobre los números enteros

Si es un polinomio univariado sobre los números enteros, que se supone libre de contenido y cuadrado , se comienza calculando una cota tal que cualquier factor tenga coeficientes de valor absoluto acotado por . De esta manera, si es un número entero mayor que , y si es un módulo conocido , entonces se puede reconstruir a partir de su imagen mod . ${\ Displaystyle f (x)}$${\ Displaystyle B}$${\ Displaystyle g (x)}$${\ Displaystyle B}$${\ Displaystyle m}$${\ Displaystyle 2B}$${\ Displaystyle g (x)}$${\ Displaystyle m}$${\ Displaystyle g (x)}$${\ Displaystyle m}$

El algoritmo de Zassenhaus procede de la siguiente manera. Primero, elija un número primo tal que la imagen de mod permanezca libre de cuadrados y del mismo grado que . Luego factoriza mod . Esto produce polinomios enteros cuyo producto coincide con mod . A continuación, aplique el lifting de Hensel ; esto actualiza el de tal manera que su producto coincide con mod , donde es lo suficientemente grande que excede : por lo tanto, cada uno corresponde a un polinomio entero bien definido. Módulo , el polinomio tiene factores (hasta unidades): los productos de todos los subconjuntos de mod . Estos factores módulo no necesitan corresponder a factores "verdaderos" de in , pero podemos probarlos fácilmente dividiéndolos en . De esta manera, todos los factores verdaderos irreductibles se pueden encontrar marcando en la mayoría de los casos, reducidos a casos omitiendo complementos. Si es reducible, el número de casos se reduce aún más eliminando aquellos que aparecen en un factor verdadero ya encontrado. El algoritmo de Zassenhaus procesa cada caso (cada subconjunto) rápidamente, sin embargo, en el peor de los casos, considera un número exponencial de casos. ${\ Displaystyle p}$${\ Displaystyle f (x)}$${\ Displaystyle p}$${\ Displaystyle f (x)}$${\ Displaystyle f (x)}$${\ Displaystyle p}$${\ Displaystyle f_ {1} (x), ..., f_ {r} (x)}$${\ Displaystyle f (x)}$${\ Displaystyle p}$${\ Displaystyle f_ {i} (x)}$${\ Displaystyle f (x)}$${\ Displaystyle p ^ {a}}$${\ Displaystyle a}$${\ Displaystyle p ^ {a}}$${\ Displaystyle 2B}$${\ Displaystyle f_ {i} (x)}$${\ Displaystyle p ^ {a}}$${\ Displaystyle f (x)}$${\ Displaystyle 2 ^ {r}}$${\ Displaystyle {f_ {1} (x), ..., f_ {r} (x)}}$${\ Displaystyle p ^ {a}}$${\ Displaystyle p ^ {a}}$${\ Displaystyle f (x)}$${\ Displaystyle \ mathbb {Z} [x]}$${\ Displaystyle \ mathbb {Z} [x]}$${\ Displaystyle 2 ^ {r}}$${\ Displaystyle 2 ^ {r-1}}$${\ Displaystyle f (x)}$${\ Displaystyle f_ {i} (x)}$

El primer algoritmo de tiempo polinomial para factorizar polinomios racionales fue descubierto por Lenstra, Lenstra y Lovász y es una aplicación del algoritmo de reducción de la base de celosía (LLL) de Lenstra-Lenstra-Lovász ( Lenstra, Lenstra y Lovász 1982 ). Una versión simplificada del algoritmo de factorización LLL es la siguiente: calcule una raíz compleja (o p -ádica) α del polinomio con alta precisión, luego use el algoritmo de reducción de la base de celosía Lenstra – Lenstra – Lovász para encontrar una relación lineal aproximada entre 1 , α, alfa ² , α ³ ,. . . con coeficientes enteros, que pueden ser una relación lineal exacta y un factor polinómico de . Se puede determinar un límite para la precisión que garantiza que este método produce un factor o una prueba de irreductibilidad. Aunque este método termina en tiempo polinomial, no se usa en la práctica porque la celosía tiene una dimensión alta y entradas enormes, lo que hace que el cálculo sea lento. ${\ Displaystyle f (x)}$${\ Displaystyle f (x)}$

La complejidad exponencial en el algoritmo de Zassenhaus proviene de un problema combinatorio: cómo seleccionar los subconjuntos correctos de . Las implementaciones de factorización de última generación funcionan de manera similar a Zassenhaus, excepto que el problema combinatorio se traduce en un problema de celosía que luego es resuelto por LLL. En este enfoque, LLL no se utiliza para calcular coeficientes de factores, sino más bien para calcular vectores con entradas en {0,1} que codifican los subconjuntos correspondientes a los factores verdaderos irreducibles. ${\ Displaystyle f_ {1} (x), ..., f_ {r} (x)}$${\ Displaystyle r}$${\ Displaystyle f_ {1} (x), ..., f_ {r} (x)}$

Factorizar extensiones algebraicas (método de Trager)

Podemos factorizar un polinomio , donde el campo es una extensión finita de . Primero, usando factorización libre de cuadrados , podemos suponer que el polinomio es libre de cuadrados. A continuación definimos el anillo cociente de grados ; este no es un campo a menos que sea ​​irreducible, pero es un anillo reducido ya que no tiene cuadrados. De hecho, si${\ Displaystyle p (x) \ en K [x]}$${\ Displaystyle K}$${\ Displaystyle \ mathbb {Q}}$ ${\ Displaystyle L = K [x] / p (x)}$${\ Displaystyle n = [L: \ mathbb {Q}] = \ deg p (x) \, [K: \ mathbb {Q}]}$${\ Displaystyle p (x)}$${\ Displaystyle p (x)}$

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

es la factorización deseada de p ( x ), el anillo se descompone únicamente en campos como:

${\ Displaystyle L = K [x] / p (x) \ cong \ prod _ {i = 1} ^ {m} K [x] / p_ {i} (x).}$

Encontraremos esta descomposición sin conocer la factorización. Primero, escribimos L explícitamente como un álgebra over : elegimos un elemento aleatorio , que genera over con alta probabilidad por el teorema del elemento primitivo . Si este es el caso, podemos calcular el polinomio mínimo de más , encontrando una relación entre -linear 1, α ,. . . , α ⁿ . Usando un algoritmo de factorización para poliomios racionales, factorizamos en irreducibles en : ${\ Displaystyle \ mathbb {Q}}$${\ Displaystyle \ alpha \ en L}$${\ Displaystyle L}$${\ Displaystyle \ mathbb {Q}}$${\ Displaystyle q (y) \ in \ mathbb {Q} [y]}$${\ Displaystyle \ alpha}$${\ Displaystyle \ mathbb {Q}}$${\ Displaystyle \ mathbb {Q}}$${\ Displaystyle \ mathbb {Q} [y]}$

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

Así tenemos:

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

donde corresponde a . Debe ser isomorfo a la descomposición previa de . ${\ Displaystyle \ alpha}$${\ Displaystyle y \ leftrightarrow (y, y, \ ldots, y)}$${\ Displaystyle L}$

Los generadores de L son x junto con los generadores de over ; escribiendo estos como polinomios en , podemos determinar las incrustaciones de y en cada componente . Al encontrar el polinomio mínimo de in , calculamos y, por lo tanto, factorizamos sobre${\ Displaystyle K}$${\ Displaystyle \ mathbb {Q}}$${\ Displaystyle \ alpha}$${\ Displaystyle x}$${\ Displaystyle K}$${\ Displaystyle \ mathbb {Q} [y] / q_ {i} (y) = K [x] / p_ {i} (x)}$${\ Displaystyle x}$${\ Displaystyle \ mathbb {Q} [y] / q_ {i} (y)}$${\ Displaystyle p_ {i} (x)}$${\ Displaystyle p (x)}$${\ Displaystyle K.}$

Ver también

• Factorización § Polinomios , para métodos heurísticos elementales y fórmulas explícitas

Bibliografía

• Fröhlich, A .; Shepherson, JC (1955), "Sobre la factorización de polinomios en un número finito de pasos", Mathematische Zeitschrift , 62 (1): 331–334, doi : 10.1007 / BF01180640 , ISSN  0025-5874
• Trager, BM (1976), "Factorización algebraica e integración de funciones racionales" , Proc. SYMSAC 76 , Symsac '76: 219–226, doi : 10.1145 / 800205.806338
• Bernard Beauzamy, Per Enflo , Paul Wang (octubre de 1994). "Estimaciones cuantitativas de polinomios en una o varias variables: desde el análisis y la teoría de números hasta el cálculo simbólico y masivamente paralelo". Revista de Matemáticas . 67 (4): 243-257. doi : 10.2307 / 2690843 . JSTOR  2690843 .CS1 maint: varios nombres: lista de autores ( enlace ) (accesible a lectores con licenciatura en matemáticas)
• Cohen, Henri (1993). Un curso de teoría de números algebraica computacional . Textos de Posgrado en Matemáticas. 138 . Berlín, Nueva York: Springer-Verlag . ISBN 978-3-540-55640-4. Señor  1228206 .
• Kaltofen, Erich (1982), "Factorización de polinomios", en B. Buchberger; R. Loos; G. Collins (eds.), Álgebra informática , Springer Verlag, págs. 95-113, CiteSeerX  10.1.1.39.7916
• Knuth, Donald E (1997). "4.6.2 Factorización de polinomios". Algoritmos seminuméricos . El arte de la programación informática . 2 (Tercera ed.). Reading, Massachusetts: Addison-Wesley. págs. 439–461, 678–691. ISBN 978-0-201-89684-8.
• Lenstra, AK ; Lenstra, HW; Lovász, László (1982). "Factorizar polinomios con coeficientes racionales". Mathematische Annalen . 261 (4): 515–534. CiteSeerX  10.1.1.310.318 . doi : 10.1007 / BF01457454 . ISSN  0025-5831 . Señor  0682664 .
• Van der Waerden , Álgebra (1970), trad. Blum y Schulenberger, Frederick Ungar.

Otras lecturas

• Kaltofen, Erich (1990), "Polynomial Factorization 1982-1986", en DV Chudnovsky; RD Jenks (eds.), Computers in Mathematics , Lecture Notes in Pure and Applied Mathematics, 125 , Marcel Dekker, Inc., CiteSeerX  10.1.1.68.7461
• Kaltofen, Erich (1992), "Factorización polinomial 1987-1991" (PDF) , Actas de Latin '92 , Springer Lect. Notas Comput. Sci., 583 , Springer , consultado el 14 de octubre de 2012
• Ivanyos, Gabor; Marek, Karpinski; Saxena, Nitin (2009), "Esquemas de factorización polinómica determinista", Proc. ISSAC 2009 : 191–198, arXiv : 0804.1974 , doi : 10.1145 / 1576702.1576730 , ISBN 9781605586090