Fatoração de polinômios - Factorization of polynomials

Em matemática e álgebra computacional , a fatoração de polinômios ou fatoração polinomial expressa um polinômio com coeficientes em um determinado campo ou em inteiros como o produto de fatores irredutíveis com coeficientes no mesmo domínio. A fatoração polinomial é um dos componentes fundamentais dos sistemas de álgebra computacional .

O primeiro algoritmo de fatoração polinomial foi publicado por Theodor von Schubert em 1793. Leopold Kronecker redescobriu o algoritmo de Schubert em 1882 e o estendeu para polinômios multivariados e coeficientes em uma extensão algébrica. Mas a maior parte do conhecimento sobre este tópico não é mais antigo do que cerca de 1965 e os primeiros sistemas de álgebra computacional :

Quando os algoritmos de etapas finitas, há muito conhecidos, foram colocados em computadores pela primeira vez, eles se mostraram altamente ineficientes. O fato de que quase qualquer polinômio uni ou multivariado de grau de até 100 e com coeficientes de tamanho moderado (até 100 bits) pode ser fatorado por algoritmos modernos em poucos minutos de tempo de computador indica o quão bem este problema foi atacado durante nos últimos quinze anos. (Erich Kaltofen, 1982)

Hoje em dia, algoritmos e computadores modernos podem fatorar rapidamente polinômios univariados de grau superior a 1000, tendo coeficientes com milhares de dígitos.

Formulação da questão

Os anéis polinomiais sobre os inteiros ou sobre um campo são domínios únicos de fatoração . Isso significa que cada elemento desses anéis é produto de uma constante e produto de polinômios irredutíveis (aqueles que não são produto de dois polinômios não constantes). Além disso, essa decomposição é única até a multiplicação dos fatores por constantes invertíveis.

A fatoração depende do campo base. Por exemplo, o teorema fundamental da álgebra , o que indica que cada polinomial com complexos coeficientes tem raízes complexas, implica que uma polinomial com coeficientes inteiros podem ser tidos (com algoritmos-encontrando raiz ) em factores lineares sobre o campo complexo C . Da mesma forma, ao longo do campo de reais , os fatores irredutíveis têm grau no máximo dois, enquanto existem polinômios de qualquer grau que são irredutíveis sobre o campo dos números racionais Q .

A questão da fatoração polinomial só faz sentido para coeficientes em um campo computável cujos todos os elementos podem ser representados em um computador e para os quais existem algoritmos para as operações aritméticas. No entanto, esta não é uma condição suficiente: Fröhlich e Shepherdson dão exemplos de tais campos para os quais nenhum algoritmo de fatoração pode existir.

Os campos de coeficientes para os quais os algoritmos de fatoração são conhecidos incluem campos primos (isto é, o campo dos racionais e aritmética modular principal ) e suas extensões de campo finitamente geradas . Coeficientes inteiros também são tratáveis. O método clássico de Kronecker é interessante apenas do ponto de vista histórico; algoritmos modernos procedem por uma sucessão de:

• Fatoração sem quadrados
• Fatoração sobre campos finitos

e reduções:

• Do caso multivariado ao caso univariado .
• De coeficientes em uma extensão puramente transcendental para o caso multivariado sobre o campo terreno (veja abaixo ).
• De coeficientes em uma extensão algébrica para coeficientes no campo terreno (veja abaixo ).
• De coeficientes racionais a coeficientes inteiros (veja abaixo ).
• De coeficientes inteiros a coeficientes em um campo primo com p elementos, para um p bem escolhido (veja abaixo ).

Parte primitiva - fatoração de conteúdo

Nesta seção, mostramos que fatorar sobre Q (os números racionais) e sobre Z (os inteiros) é essencialmente o mesmo problema.

O conteúdo de um polinômio p ∈ Z [ X ], denotado "cont ( p )", é, até seu sinal, o maior divisor comum de seus coeficientes. A parte primitiva de p é primpart ( p ) = p / cont ( p ), que é um polinômio primitivo com coeficientes inteiros. Isso define uma fatoração de p no produto de um inteiro e um polinômio primitivo. Essa fatoração é única até o signo do conteúdo. É uma convenção comum escolher o sinal do conteúdo de forma que o coeficiente líder da parte primitiva seja positivo.

Por exemplo,

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

é uma fatoração em conteúdo e parte primitiva.

Todo polinômio q com coeficientes racionais pode ser escrito

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

onde p ∈ Z [ X ] ec ∈ Z : basta tomar para c um múltiplo de todos os denominadores dos coeficientes de q (por exemplo, seu produto) ep = cq . O conteúdo de q é definido como:

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

e a parte primitiva de q é a de p . Quanto aos polinômios com coeficientes inteiros, isso define uma fatoração em um número racional e um polinômio primitivo com coeficientes inteiros. Esta fatoração também é única dependendo da escolha de um sinal.

Por exemplo,

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

é uma fatoração em conteúdo e parte primitiva.

Gauss provou que o produto de dois polinômios primitivos também é primitivo ( lema de Gauss ). Isso implica que um polinômio primitivo é irredutível sobre os racionais se e somente se for irredutível sobre os inteiros. Isso implica também que a fatoração sobre os racionais de um polinômio com coeficientes racionais é a mesma que a fatoração sobre os inteiros de sua parte primitiva. Da mesma forma, a fatoração sobre os inteiros de um polinômio com coeficientes inteiros é o produto da fatoração de sua parte primitiva pela fatoração de seu conteúdo.

Em outras palavras, um cálculo de GCD inteiro reduz a fatoração de um polinômio sobre os racionais para a fatoração de um polinômio primitivo com coeficientes inteiros e a fatoração sobre os inteiros para a fatoração de um inteiro e um polinômio primitivo.

Tudo o que precede permanece verdadeiro se Z é substituído por um anel polinomial sobre um campo F e Q é substituído por um campo de funções racionais sobre F nas mesmas variáveis, com a única diferença de que "até um sinal" deve ser substituído por " até a multiplicação por uma constante invertível em F ". Isso reduz a fatoração mais de um puramente transcendental extensão campo de F para a fatoração de polinômios multivariados mais de F .

Fatoração sem quadrados

Se dois ou mais fatores de um polinômio são idênticos, o polinômio é um múltiplo do quadrado desse fator. O fator múltiplo também é um fator da derivada do polinômio (com relação a qualquer uma das variáveis, se várias).

Para polinômios univariados, múltiplos fatores são equivalentes a múltiplas raízes (em um campo de extensão adequado). Para polinômios univariados sobre os racionais (ou mais geralmente sobre um campo de zero característico ), o algoritmo de Yun explora isso para fatorar eficientemente o polinômio em fatores livres de quadrados, ou seja, fatores que não são múltiplos de um quadrado, realizando uma sequência de Cálculos GCD começando com gcd ( f ( x ), f '( x )). Para fatorar o polinômio inicial, é suficiente fatorar cada fator livre de quadrados. A fatoração sem quadrados é, portanto, o primeiro passo na maioria dos algoritmos de fatoração polinomial.

O algoritmo de Yun estende isso ao caso multivariado, considerando um polinômio multivariado como um polinômio univariado sobre um anel polinomial.

No caso de um polinômio sobre um campo finito, o algoritmo de Yun se aplica apenas se o grau for menor que a característica, porque, caso contrário, a derivada de um polinômio diferente de zero pode ser zero (sobre o campo com p elementos, a derivada de um polinômio em x ^p é sempre zero). No entanto, uma sucessão de cálculos GCD, a partir do polinômio e sua derivada, permite calcular a decomposição livre de quadrados; veja Fatoração polinomial sobre campos finitos # Fatoração sem quadrados .

Métodos clássicos

Esta seção descreve métodos de livros que podem ser convenientes ao calcular manualmente. Esses métodos não são usados ​​para cálculos de computador porque eles usam a fatoração de inteiros , que atualmente é mais lenta do que a fatoração polinomial.

Obtenção de fatores lineares

Todos os fatores lineares com coeficientes racionais podem ser encontrados usando o teste de raiz racional . Se o polinômio a ser fatorado for , então todos os fatores lineares possíveis são da forma , onde é um fator inteiro de e é um fator inteiro de . Todas as combinações possíveis de fatores inteiros podem ser testadas para validade, e cada uma válida pode ser fatorada usando divisão longa polinomial . Se o polinômio original é o produto de fatores pelo menos dois dos quais são de grau 2 ou superior, esta técnica fornece apenas uma fatoração parcial; caso contrário, a fatoração está completa. Em particular, se houver exatamente um fator não linear, ele será o polinômio restante após todos os fatores lineares terem sido fatorados. No caso de um polinômio cúbico , se a cúbica for fatorável, o teste de raiz racional fornece uma fatoração completa, seja em um fator linear e em um fator quadrático irredutível, ou em três fatores lineares. ${\ 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}}$

Método de Kronecker

Uma vez que polinômios inteiros devem ser fatorados em fatores polinomiais inteiros, e a avaliação de polinômios inteiros em valores inteiros deve produzir números inteiros, os valores inteiros de um polinômio podem ser fatorados em apenas um número finito de maneiras e produzir apenas um número finito de possíveis fatores polinomiais.

Por exemplo, considere

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

Se este polinômio for fatorado por Z , então pelo menos um de seus fatores deve ser de grau dois ou menos, portanto, é determinado exclusivamente por três valores . Assim, calculamos três valores , e . Se um desses valores for 0, temos um fator linear. Se os valores forem diferentes de zero, podemos listar as fatorações possíveis para cada um. Agora, 2 só pode ser fatorado 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) ou (−2) × (−1).

Portanto, se um fator polinomial inteiro de segundo grau existe, ele deve assumir um dos valores

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

e da mesma forma para p (1). Existem oito fatorações de 6 (quatro cada para 1 × 6 e 2 × 3), perfazendo um total de 4 × 4 × 8 = 128 triplas possíveis ( p (0), p (1), p (−1)), dos quais metade pode ser descartada como os negativos da outra metade. Portanto, devemos verificar 64 polinômios inteiros explícitos como possíveis fatores de . Testá-los exaustivamente revela que ${\ displaystyle p (x) = ax ^ {2} + bx + c}$${\ displaystyle f (x)}$

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

construído a partir de ( g (0), g (1), g (−1)) = (1,3,1) fatores . ${\ displaystyle f (x)}$

Dividindo f ( x ) por p ( x ) dá o outro fator , de modo que . Agora, pode-se testar recursivamente para encontrar os fatores de p ( x ) eq ( x ), neste caso usando o teste de raiz racional. Acontece que ambos são irredutíveis, então a fatoração irredutível de f ( x ) é: ${\ 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

Fatoração sobre campos finitos

Fatorar polinômios univariados sobre os inteiros

Se é um polinômio univariada sobre os inteiros, assumido como sendo de conteúdo livre e square-livre , começa por calcular um limite tal que qualquer fator tem coeficientes de valor absoluto delimitada por . Desta forma, se for um inteiro maior que , e se for um módulo conhecido , então pode ser reconstruído a partir de seu mod de imagem . ${\ displaystyle f (x)}$${\ displaystyle B}$${\ displaystyle g (x)}$${\ displaystyle B}$${\ displaystyle m}$${\ displaystyle 2B}$${\ displaystyle g (x)}$${\ displaystyle m}$${\ displaystyle g (x)}$${\ displaystyle m}$

O algoritmo Zassenhaus procede da seguinte forma. Primeiro, escolha um número primo de forma que a imagem do mod permaneça sem quadrados e do mesmo grau que . Então fator mod . Isso produz polinômios inteiros cujo produto corresponde ao mod . Em seguida, aplique o levantamento Hensel ; isso atualiza o de tal forma que seu produto corresponde ao mod , onde é grande o suficiente para exceder : assim, cada um corresponde a um polinômio inteiro bem definido. Módulo , o polinômio tem fatores (até unidades): os produtos de todos os subconjuntos de mod . O módulo desses fatores não precisa corresponder aos fatores "verdadeiros" de in , mas podemos testá-los facilmente dividindo-os em . Desta forma, todos os verdadeiros fatores irredutíveis podem ser encontrados verificando na maioria dos casos, reduzidos a casos pulando complementos. Se for redutível, o número de casos é reduzido ainda mais removendo aqueles que aparecem em um fator verdadeiro já encontrado. O algoritmo Zassenhaus processa cada caso (cada subconjunto) rapidamente, porém, no pior caso, ele considera um 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)}$

O primeiro algoritmo de tempo polinomial para fatorar polinômios racionais foi descoberto por Lenstra, Lenstra e Lovász e é uma aplicação do algoritmo de redução da base da rede (LLL) Lenstra – Lenstra – Lovász ( Lenstra, Lenstra & Lovász 1982 ). Uma versão simplificada do algoritmo de fatoração LLL é a seguinte: calcule uma raiz complexa (ou p -adica) α do polinômio para alta precisão e, em seguida, use o algoritmo de redução da base de rede Lenstra – Lenstra – Lovász para encontrar uma relação linear aproximada entre 1 , α, a- ² , α ³ ,. . . com coeficientes inteiros, que podem ser uma relação linear exata e um fator polinomial de . Pode-se determinar um limite para a precisão que garante que esse método produza um fator ou uma prova de irredutibilidade. Embora este método termine em tempo polinomial, ele não é usado na prática porque a rede possui grande dimensão e grandes entradas, o que torna o cálculo lento. ${\ displaystyle f (x)}$${\ displaystyle f (x)}$

A complexidade exponencial no algoritmo de Zassenhaus vem de um problema combinatório: como selecionar os subconjuntos corretos de . Implementações de fatoração de última geração funcionam de maneira semelhante a Zassenhaus, exceto que o problema combinatório é traduzido para um problema de rede que é então resolvido por LLL. Nesta abordagem, LLL não é usado para calcular coeficientes de fatores, mas sim para calcular vetores com entradas em {0,1} que codificam os subconjuntos correspondentes aos fatores verdadeiros irredutíveis. ${\ displaystyle f_ {1} (x), ..., f_ {r} (x)}$${\ displaystyle r}$${\ displaystyle f_ {1} (x), ..., f_ {r} (x)}$

Fatoração sobre extensões algébricas (método de Trager)

Podemos fatorar um polinômio , onde o campo é uma extensão finita de . Primeiro, usando a fatoração livre de quadrados , podemos supor que o polinômio é livre de quadrados. Em seguida, definimos o anel quociente de grau ; este não é um campo a menos que seja irredutível, mas é um anel reduzido, uma vez que não tem quadrados. Na verdade, se${\ displaystyle p (x) \ in 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)}$

é a fatoração desejada de p ( x ), o anel se decompõe exclusivamente em campos como:

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

Encontraremos essa decomposição sem conhecer a fatoração. Primeiro, escrevemos L explicitamente como uma álgebra over : pegamos um elemento aleatório , que gera over com alta probabilidade pelo teorema do elemento primitivo . Se for esse o caso, podemos calcular o polinômio mínimo de over , encontrando uma relação -linear entre 1, α ,. . . , α ⁿ . Usando um algoritmo de fatoração para polômios racionais, fatoramos em irredutíveis em : ${\ displaystyle \ mathbb {Q}}$${\ displaystyle \ alpha \ in 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).}$

Assim, temos:

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

onde corresponde a . Deve ser isomórfico à decomposição anterior de . ${\ displaystyle \ alpha}$${\ displaystyle y \ leftrightarrow (y, y, \ ldots, y)}$${\ displaystyle L}$

Os geradores de L são x junto com os geradores de over ; escrevendo-os como polinômios em , podemos determinar os embeddings de e em cada componente . Ao encontrar o polinômio mínimo de em , calculamos , e, portanto, fator mais${\ 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.}$

Veja também

• Fatoração § Polinômios , para métodos heurísticos elementares e fórmulas explícitas

Bibliografia

• Fröhlich, A .; Shepherson, JC (1955), "On the factorisation of polynomials in a finite number of steps", Mathematische Zeitschrift , 62 (1): 331-334, doi : 10.1007 / BF01180640 , ISSN  0025-5874
• Trager, BM (1976), "Algebraic Factoring and Rational Function Integration" , Proc. SYMSAC 76 , Symsac '76: 219–226, doi : 10.1145 / 800205.806338
• Bernard Beauzamy, Per Enflo , Paul Wang (outubro de 1994). "Estimativas quantitativas para polinômios em uma ou várias variáveis: da análise e teoria dos números à computação simbólica e maciçamente paralela". Revista Matemática . 67 (4): 243–257. doi : 10.2307 / 2690843 . JSTOR  2690843 .CS1 maint: vários nomes: lista de autores ( link ) (acessível a leitores com graduação em matemática)
• Cohen, Henri (1993). Um curso de teoria algébrica computacional dos números . Textos de Pós-Graduação em Matemática. 138 . Berlim, Nova York: Springer-Verlag . ISBN 978-3-540-55640-4. MR  1228206 .
• Kaltofen, Erich (1982), "Factorization of polynomials", em B. Buchberger; R. Loos; G. Collins (eds.), Computer Algebra , Springer Verlag, pp. 95-113, CiteSeerX  10.1.1.39.7916
• Knuth, Donald E (1997). "4.6.2 Factorização de Polinômios". Algoritmos Seminuméricos . The Art of Computer Programming . 2 (Terceira edição). Reading, Massachusetts: Addison-Wesley. pp. 439-461, 678-691. ISBN 978-0-201-89684-8.
• Lenstra, AK ; Lenstra, HW; Lovász, László (1982). "Fatoração de polinômios com coeficientes racionais". Mathematische Annalen . 261 (4): 515–534. CiteSeerX  10.1.1.310.318 . doi : 10.1007 / BF01457454 . ISSN  0025-5831 . MR  0682664 .
• Van der Waerden , Algebra (1970), trad. Blum e Schulenberger, Frederick Ungar.

Leitura adicional

• Kaltofen, Erich (1990), "Polynomial Factorization 1982-1986", em 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), "Polynomial Factorization 1987-1991" (PDF) , Proceedings of Latin '92 , Springer Lect. Notes Comput. Sci., 583 , Springer , recuperado em 14 de outubro de 2012
• Ivanyos, Gabor; Marek, Karpinski; Saxena, Nitin (2009), "Schemes for Deterministic Polynomial Factoring", Proc. ISSAC 2009 : 191–198, arXiv : 0804.1974 , doi : 10.1145 / 1576702.1576730 , ISBN 9781605586090