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,

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

é unha factorización en contido e parte primitiva.

Todo polinomio q con coeficientes racionais pódese escribir

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

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

Por exemplo,

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

é unha factorización en contido e parte primitiva.

Factorización libre de cadrados

Artigo principal: Polinomio 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 $f(x)$ é un polinomio con coeficientes enteiros, entón $f(a)$ é un número enteiro en canto a é un número enteiro. Só hai un número finito de posíbeis valores enteiros para un factor de a. Entón, se $g(x)$ é un factor de $f(x),$ o valor de $g(a)$ debe ser un dos factores de $f(a).$

Por exemplo, considere

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

Se este polinomio factoriza sobre Z, entón polo menos un dos seus factores $p(x)$ debe ser de grao dous ou menos, polo que $p(x)$ está determinado de forma única por tres valores. Así, calculamos tres valores $f(0)=2$, $f(1)=6$ e $f(-1)=2$. 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 $p(x)=ax^{2}+bx+c$ como posíbeis factores de $f(x)$. Probados exhaustivamente revela que

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

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

Dividindo f(x) entre p(x) dá o outro factor $q(x)=x^{3}-x+2$, e así temos $f(x)=p(x)q(x)$.

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

Artigos principais: Factorización de polinomios sobre corpos finitos, Algoritmo de Berlekamp e Algoritmo de Cantor-Zassenhaus.

Factorización de polinomios univariados sobre números enteiros

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

O algoritmo de Zassenhaus procede do seguinte xeito. En primeiro lugar, escolle un número primo $p$ de xeito que a imaxe de $f(x){\bmod {p}}$ permaneza libre de cadrados, e do mesmo grao que $f(x)$.

Entón factorizamos $f(x){\bmod {p}}$. Isto produce polinomios enteiros $f_{1}(x),\ldots ,f_{r}(x)$ cuxo produto coincide con $f(x){\bmod {p}}$. A continuación, aplicamos a elevación de Hensel; isto actualiza $f_{i}(x)$ de tal xeito que o seu produto coincide con $f(x){\bmod {p}}^{a}$, onde $a$ é o suficientemente grande como para que $p^{a}$ supere $2B$: así, cada $f_{i}(x)$ corresponde a un polinomio en enteiros ben definido.

O polinomio $f(x)$ módulo $p^{a}$ ten factores $2^{r}$ (ata unidades): os produtos de todos os subconxuntos de $\{f_{1}(x),\ldots ,f_{r}(x)\}{\bmod {p}}^{a}$. Estes factores módulo $p^{a}$ non precisan corresponderse con factores "verdadeiros" de $f(x)$ en $\mathbb {Z} [x]$, mais podemos probalos facilmente por división en $\mathbb {Z} [x]$.

Deste xeito, todos os factores verdadeiros irredutíbeis pódense atopar comprobando como máximo $2^{r}$ casos, reducidos a $2^{r-1}$ casos saltando complementos. Se $f(x)$ é redutíbel, o número de casos redúcese aínda máis eliminando aqueles $f_{i}(x)$ 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) (Lenstra, Lenstra & Lovász 1982).

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 $p(x)\in K[x]$, onde o corpo $K$ é unha extensión finita de $\mathbb {Q}$. En primeiro lugar, facemos o polinomio libre de cadrados.

A continuación definimos o anel cociente $L=K[x]/p(x)$ de grao $n=[L:\mathbb {Q} ]=\deg p(x)\,[K:\mathbb {Q} ]$; este non é un corpo a menos que $p(x)$ sexa irredutíbel, mais é un anel reducido xa que $p(x)$ é libre de cadrados. En efecto, se

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

é a factorización desexada de p(x), o anel descompónse unicamente en corpos como:

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

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

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

Así temos:

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

onde $\alpha$ corresponde a $y\leftrightarrow (y,y,\ldots ,y)$. Esta debe ser isomorfa á descomposición anterior de $L$.

Os xeradores de L son x xunto cos xeradores de $K$ sobre $\mathbb {Q}$; escribindo estes como polinomios en $\alpha$, podemos determinar os mergullos de $x$ e $K$ en cada compoñente $\mathbb {Q} [y]/q_{i}(y)=K[x]/p_{i}(x)$. Ao atopar o polinomio mínimo de $x$ en $\mathbb {Q} [y]/q_{i}(y)$, calculamos $p_{i}(x)$, e polo tanto factorizamos $p(x)$ sobre $K.$

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.

Véxase tamén

Bibliografía

• Fröhlich, A.; Shepherson, J. C. (1955). On the factorisation of polynomials in a finite number of steps. Mathematische Zeitschrift 62. pp. 331–334. ISSN 0025-5874. doi:10.1007/BF01180640. 
• Trager, B.M. (1976). "Algebraic factoring and rational function integration". Proceedings of the third ACM symposium on Symbolic and algebraic computation - SYMSAC '76. pp. 219–226. ISBN 9781450377904. doi:10.1145/800205.806338. 
• Bernard Beauzamy, Per Enflo, Paul Wang (October 1994). "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. Computer Algebra. Springer Verlag. pp. 95–113. 
• Knuth, Donald E (1997). "4.6.2 Factorization of Polynomials". Seminumerical Algorithms. The Art of Computer Programming 2 (Third ed.). Reading, Massachusetts: Addison-Wesley. pp. 439–461, 678–691. ISBN 978-0-201-89684-8. 
• 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.
• Kaltofen, Erich (1990). "Polynomial Factorization 1982-1986". En D. V. Chudnovsky; R. D. Jenks. Computers in Mathematics. Lecture Notes in Pure and Applied Mathematics 125. Marcel Dekker, Inc. 
• Kaltofen, Erich (1992). "Polynomial Factorization 1987–1991" (PDF). Proceedings of Latin '92. Springer Lect. Notes Comput. Sci. 583. Springer. Consultado o October 14, 2012. 
• Ivanyos, Gabor; Marek, Karpinski; Saxena, Nitin (2009). "Schemes for deterministic polynomial factoring". Proceedings of the 2009 international symposium on Symbolic and algebraic computation. pp. 191–198. ISBN 9781605586090. arXiv:0804.1974. doi:10.1145/1576702.1576730. 

Outros artigos

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