Factorización de polinomios

En matemáticas e álxebra informática, a factorización de polinomios ou factorización polinómica expresa un polinomio con coeficientes nun corpo determinado ou en números enteiros como o produto de factores irredutíbleis con coeficientes no mesmo dominio. A factorización polinómica é un dos compoñentes fundamentais dos sistemas de álxebra informática.

O primeiro algoritmo de factorización polinómica foi publicado por Theodor von Schubert en 1793. Leopold Kronecker redescubriu o algoritmo de Schubert en 1882 e estendeuno a polinomios e coeficientes multivariados nunha extensión alxébrica. 

Mais a maior parte do coñecemento sobre este tema non é máis antigo que arredor de 1965 e os primeiros sistemas de álxebra informática.

 Formulación da cuestión 
Os aneis de polinomios sobre os números enteiros ou sobre un corpo son dominios de factorización única. Isto significa que todo elemento destes aneis é produto dunha constante e un produto de polinomios irredutíbeis (aqueles que non son produto de dous polinomios non constantes). A maiores, esta descomposición é única ata a multiplicación dos factores por constantes invertíbeis.

A factorización depende do corpo base. Por exemplo, o teorema fundamental da álxebra, que afirma que todo polinomio con coeficientes complexos ten raíces complexas, implica que un polinomio con coeficientes enteiros se pode factorizar (con algoritmos de busca de raíces) en factores lineares sobre o corpo complexo C. Do mesmo xeito, sobre o corpo dos reais, os factores irredutíbeis teñen grao como máximo dous, mentres que hai polinomios de calquera grao que son irredutíbeis sobre o corpo dos racionais Q.

Os corpos de coeficientes para os que se coñecen algoritmos de factorización inclúen corpos primos (é dicir, o corpo do número racional e os corpos dos enteiros módulo un número primo) e as súas extensións de corpo finitamente xeradas. Tamén se poden tratar os coeficientes enteiros. O método clásico de Kronecker só é interesante dende o punto de vista histórico; os algoritmos modernos proceden mediante unha sucesión de:

 Factorización sen cadrados
 Factorización sobre corpos finitos

e reducións:

 Do caso multivariado ao caso univariado.
 Desde coeficientes nunha extensión puramente transcendental ata o caso multivariado sobre o corpo base.
 Desde os coeficientes nunha extensión alxébrica ata os coeficientes de base.
 Desde coeficientes racionais ata coeficientes enteiros.
 Desde coeficientes enteiros ata coeficientes nun corpo primo con p elementos, para un p ben escollido.

 Factorización da parte primitiva-contido 
Nesta sección, mostramos que factorizar sobre Q (os números racionais) e sobre Z (os enteiros) é esencialmente o mesmo problema.

O contido dun polinomio p ∈ Z [ X ], denotado "cont(p )", é, ata o seu signo, o máximo común divisor dos seus coeficientes. A parte primitiva de p é primpart(p) = p/cont(p), que é un polinomio primitivo con coeficientes enteiros. 

Isto define unha factorización de p no produto dun enteiro e dun polinomio primitivo. Esta factorización é única ata o signo do contido. É unha convención habitual escoller o signo do contido de forma que o coeficiente principal da parte primitiva sexa positivo.

Por exemplo,



é unha factorización en contido e parte primitiva.

Todo polinomio q con coeficientes racionais pódese escribir



onde p ∈ Z [ X ] e c ∈ Z.

Por exemplo,



é unha factorización en contido e parte primitiva.

 Factorización libre de cadrados 

Se dous ou máis factores dun polinomio son idénticos, entón o polinomio é un múltiplo do cadrado deste factor. O factor múltiple tamén é un factor da derivada do polinomio (en relación a calquera das variábeis, se hai varias).

Para polinomios univariados, múltiples factores son equivalentes a múltiples raíces (sobre  a extensión dun corpo axeitado). Para polinomios univariados sobre os racionais (ou máis xeralmente sobre un corpo de característica cero), o algoritmo de Yun aproveita isto para factorizar eficientemente o polinomio en factores libres de cadrados, é dicir, factores que non son múltiplo dun cadrado, realizando unha secuencia de cálculos MCD comezando por mcd(f(x), f  (x)). Para factorizar o polinomio inicial abonda con factorizar cada factor libre de cadrados. A factorización sen cadrados é polo tanto o primeiro paso na maioría dos algoritmos de factorización polinómica.

 Métodos clásicos 
Esta sección describe un método de libros de texto que pode ser conveniente cando se computa a man. Estes métodos non se usan para cálculos informáticos porque usan a factorización de enteiros, que actualmente é máis lenta que a factorización polinómica.

 Método de Kronecker 
O método de Kronecker ten como obxectivo factorizar polinomios univariados con coeficientes enteiros en polinomios con coeficientes enteiros.

O método utiliza o feito de que a avaliación de polinomios enteiros en valores enteiros debe producir números enteiros. É dicir, se  é un polinomio con coeficientes enteiros, entón  é un número enteiro en canto  é un número enteiro. Só hai un número finito de posíbeis valores enteiros para un factor de . Entón, se  é un factor de  o valor de  debe ser un dos factores de 

Por exemplo, considere

  .

Se este polinomio factoriza sobre Z''', entón polo menos un dos seus factores  debe ser de grao dous ou menos, polo que  está determinado de forma única por tres valores. Así, calculamos tres valores ,  e . Se un destes valores é 0, xa temos un factor linear. Se os valores son distintos de cero, podemos enumerar as posíbeis factorizacións para cada unha. 

Agora, 2 só pode factorizar como

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

Polo tanto, se existe un factor polinómico enteiro de segundo grao, debe tomar un dos valores

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

e igualmente para p (-1). Hai oito factorizacións de 6 (catro cada unha para 1×6 e 2×3), o que fai un total de 4×4×8 = 128 posíbeis ternas (p(0), p(1), p(−1)), das que a metade se poden descartar como negativos da outra metade. Así, debemos comprobar 64 polinomios enteiros explícitos  como posíbeis factores de . Probados exhaustivamente revela que



construído a partir de (g(0), g(1), g(−1)) = (1,3,1) factoriza .

Dividindo f(x) entre p(x) dá o outro factor , e así temos . 

Agora procedemos recursivamente para atopar factores de p(x) e q (x), neste caso usando a proba da raíz racional. Resulta que ambos os dous son irredutíbeis, polo que a factorización irredutíbel de f (x) é: 

 Métodos modernos 

 Factorización sobre corpos finitos 

 Factorización de polinomios univariados sobre números enteiros 
Se  é un polinomio univariado sobre os enteiros, que se supón libre de contido e libre de cadrados, comezamos calculando un límite  tal que calquera factor  ten coeficientes de valor absoluto limitados por . Deste xeito, se  é un número enteiro maior que , e se coñecemos   módulo , entón  pódese reconstruír a partir da súa imaxe mod . 

O algoritmo de Zassenhaus procede do seguinte xeito. En primeiro lugar, escolle un número primo  de xeito que a imaxe de  permaneza libre de cadrados, e do mesmo grao que . 

Entón factorizamos . Isto produce polinomios enteiros  cuxo produto coincide con . A continuación, aplicamos a elevación de Hensel; isto actualiza  de tal xeito que o seu produto coincide con , onde  é o suficientemente grande como para que  supere : así, cada  corresponde a un polinomio en enteiros ben definido. 

O polinomio  módulo  ten factores  (ata unidades): os produtos de todos os subconxuntos de . Estes factores módulo  non precisan corresponderse con factores "verdadeiros" de  en , mais podemos probalos facilmente por división en . 

Deste xeito, todos os factores verdadeiros irredutíbeis pódense atopar comprobando como máximo  casos, reducidos a  casos saltando complementos. Se  é redutíbel, o número de casos redúcese aínda máis eliminando aqueles  que aparecen nun factor verdadeiro xa atopado. O algoritmo de Zassenhaus procesa cada caso (cada subconxunto) rapidamente, porén, no peor dos casos, ten que procesar un número exponencial de casos.

O primeiro algoritmo de tempo polinómico para factorizar polinomios racionais foi descuberto por Lenstra, Lenstra e Lovász sendo unha aplicación do  algoritmo de redución de bases de retícula de Lenstra-Lenstra-Lovász (LLL) . 

Aínda que este método remata en tempo polinómico, non se usa na práctica porque a retícula ten grandes dimensións e entradas enormes, o que fai que o cálculo sexa lento.

 Factorización sobre extensións alxébricas (método de Trager) 
Podemos factorizar un polinomio , onde o corpo  é unha extensión finita de . En primeiro lugar, facemos o polinomio libre de cadrados. 

A continuación definimos o anel cociente  de grao ; este non é un corpo a menos que  sexa irredutíbel, mais é un anel reducido xa que  é libre de cadrados. En efecto, seé a factorización desexada de p(x), o anel descompónse unicamente en corpos como:



Atoparemos esta descomposición sen coñecer a factorización. En primeiro lugar, escribimos L explicitamente como unha álxebra : escollemos un elemento aleatorio , que xera  sobre  con alta probabilidade polo teorema dos elementos primitivos. Se este é o caso, podemos calcular o polinomio mínimo  de  sobre , ao atopar a relación lineal en   entre 1, α, . . . , αn. Usando un algoritmo de factorización para poliomios racionais, factorizamos en irredutíbeis en :



Así temos:



onde  corresponde a . Esta debe ser isomorfa á descomposición anterior de .

Os xeradores de L son x xunto cos xeradores de  sobre ; escribindo estes como polinomios en , podemos determinar os mergullos  de  e  en cada compoñente . Ao atopar o polinomio mínimo de  en , calculamos , e polo tanto factorizamos   sobre 

 Factorización numérica 
A "factorización numérica" refírese habitualmente á factorización de polinomios con coeficientes reais ou complexos, cuxos coeficientes só se coñecen aproximadamente, polo xeral porque se representan como números de coma flotante.

Para polinomios univariados con coeficientes complexos, a factorización pódese reducir facilmente ao cálculo numérico de raíces polinómicas e multiplicidades.

Desenvolvéronse e implementáronse varios algoritmos para a factorización numérica sendo aínda un tema de investigación en curso. 
 Notas 


 Véxase tamén 

 Bibliografía 

  (accessible to readers with undergraduate mathematics)



 Van der Waerden, Algebra'' (1970), trans. Blum and Schulenberger, Frederick Ungar.




 Outros artigos 
 Polinomio
 Aritmética modular
 Factorización de polinomios sobre corpos finitos

Categoría:Polinomios
Categoría:Wikipedia:Páxinas con traducións non revisadas