Fatoração polinomial

Todos os fatores lineares com coeficientes racionais podem ser encontrados usando o teste das raízes racionais. Se o polinômio a ser fatorado é ${\displaystyle a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{1}x+a_{0}}$, então todos os possíveis fatores lineares são da forma ${\displaystyle b_{1}x-b_{0}}$, onde ${\displaystyle b_{1}}$ é um fator inteiro de ${\displaystyle a_{n}}$ e ${\displaystyle b_{0}}$ é um fator inteiro de ${\displaystyle a_{0}}$. Todas as combinações possíveis de fatores inteiros podem ser testadas quanto à validade, e cada combinação válida pode ser fatorada usando divisão polinomial. Se o polinômio original for o produto de fatores, dos quais pelo menos dois são de grau 2 ou superior, esta técnica fornece apenas uma fatoração parcial; caso contrário a fatoração é completa. Em particular, se houver exatamente um fator não linear, ele será o polinômio que sobrar depois que todos os fatores lineares tiverem sido fatorados. No caso de um polinômio cúbico, se o cúbico for fatorável de todo, o teste da raiz racional dá uma fatoração completa, seja num fator linear e um fator quadrático irredutível, ou em três fatores lineares.

O método de Kronecker tem como objetivo fatorar polinômios univariados com coeficientes inteiros em polinômios com coeficientes inteiros.

O método usa o fato de que avaliar polinômios inteiros em valores inteiros deve produzir inteiros. Isto é, se ${\displaystyle f(x)}$ é um polinômio com coeficientes inteiros, então ${\displaystyle f(a)}$ é um inteiro assim que a é um inteiro. Existe apenas um número finito de possíveis valores inteiros para um fator de a. Portanto, se ${\displaystyle g(x)}$ é um fator de ${\displaystyle f(x),}$ o valor de ${\displaystyle g(a)}$ deve ser um dos fatores de ${\displaystyle f(a).}$

Se procurarmos todos os fatores de um dado grau d, podemos considerar ${\displaystyle d+1}$ valores, ${\displaystyle a_{0},\ldots ,a_{d}}$ para a, que dão um número finito de possibilidades para a tupla ${\displaystyle (f(a_{0}),\ldots ,f(a_{d})).}$ Cada ${\displaystyle f(a_{i})}$ tem um número finito de divisores ${\displaystyle b_{i,0},\ldots ,b_{i,k_{i}}}$, e cada ${\displaystyle (d+1)}$-tupla onde a ${\displaystyle i^{\text{ésima}}}$ entrada é um divisor de ${\displaystyle f(a_{i})}$, isto é, uma tupla da forma ${\displaystyle (b_{0,j_{1}},\ldots ,b_{d,j_{d}})}$, produz um polinômio único de grau no máximo ${\displaystyle d}$, que pode ser calculado por interpolação polinomial. Cada um desses polinômios pode ser testado para ser um fator por divisão polinomial. Como havia finitamente muitos ${\displaystyle a_{i}}$ e cada ${\displaystyle f(a_{i})}$ tem finitamente muitos divisores, existem finitamente muitas dessas tuplas. Assim, uma busca exaustiva permite encontrar todos os fatores de grau no máximo d.

Por exemplo, considere

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

Se este polinômio for fatorado sobre Z, então pelo menos um de seus fatores ${\displaystyle p(x)}$ deve ser de grau dois ou menor, então ${\displaystyle p(x)}$ é singularmente determinado por três valores. Assim, calculamos três valores ${\displaystyle f(0)=2}$, ${\displaystyle f(1)=6}$ e ${\displaystyle f(-1)=2}$. 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

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

Portanto, se um fator polinomial inteiro de segundo grau existir, 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 possíveis triplos (p(0), p(1), p(−1)), das quais a metade pode ser descartada como as negativas da outra metade. Assim, devemos verificar 64 polinômios inteiros explícitos ${\displaystyle p(x)=ax^{2}+bx+c}$ como possíveis fatores de ${\displaystyle f(x)}$. Testá-los exaustivamente revela que

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

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

Dividindo f(x) por p(x) dá o outro fator ${\displaystyle q(x)=x^{3}-x+2}$, de modo que ${\displaystyle f(x)=p(x)q(x)}$. Agora pode-se testar recursivamente para encontrar fatores de p(x) e q(x), neste caso usando o teste das raízes racionais. Acontece que ambos são irredutíveis, então a fatoração irredutível de f(x) é:^[5]

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

Se ${\displaystyle f(x)}$ é um polinômio univariado sobre os inteiros, suposto ser livre de conteúdo e livre de quadrados, começa-se calculando um limite ${\displaystyle B}$ de tal modo que qualquer fator ${\displaystyle g(x)}$ tenha coeficientes de valor absoluto limitados por ${\displaystyle B}$. Desta forma, se ${\displaystyle m}$ for um inteiro maior que ${\displaystyle 2B}$, e se ${\displaystyle g(x)}$ for conhecido módulo ${\displaystyle m}$, então ${\displaystyle g(x)}$ pode ser reconstruído a partir da sua imagem mod ${\displaystyle m}$.

O algoritmo de Zassenhaus procede da seguinte forma. Em primeiro lugar, escolhe-se um número primo ${\displaystyle p}$ de tal modo que a imagem de ${\displaystyle f(x){\bmod {p}}}$ permaneça livre de quadrados, e com o mesmo grau que ${\displaystyle f(x)}$. Uma escolha aleatória quase sempre satisfará estas restrições, uma vez que apenas um número finito de números primos não as satisfazem, nomeadamente os divisores primos do produto do discriminante e do coeficiente principal do polinómio. Então fatora-se ${\displaystyle f(x){\bmod {p}}}$. Isto produz os polinômios inteiros ${\displaystyle f_{1}(x),\ldots ,f_{r}(x)}$ cujo produto corresponde a ${\displaystyle f(x){\bmod {p}}}$. Em seguida, aplica-se a elevação de Hensel; esta atualiza os ${\displaystyle f_{i}(x)}$ de tal forma que o seu produto corresponde a ${\displaystyle f(x){\bmod {p}}^{a}}$, onde ${\displaystyle a}$ é grande o suficiente para que ${\displaystyle p^{a}}$ exceda ${\displaystyle 2B}$: assim cada ${\displaystyle f_{i}(x)}$ corresponde a um polinômio inteiro bem definido. Módulo ${\displaystyle p^{a}}$, o polinômio ${\displaystyle f(x)}$ tem ${\displaystyle 2^{r}}$ fatores (a menos de unidades): os produtos de todos os subconjuntos de ${\displaystyle \{f_{1}(x),\ldots ,f_{r}(x)\}{\bmod {p}}^{a}}$. Estes fatores módulo ${\displaystyle p^{a}}$ não têm de corresponder aos "verdadeiros" fatores de ${\displaystyle f(x)}$ em ${\displaystyle \mathbb {Z} [x]}$, mas podemos testá-los facilmente por divisão em ${\displaystyle \mathbb {Z} [x]}$. Desta forma, todos os fatores verdadeiros irredutíveis podem ser encontrados testando no máximo ${\displaystyle 2^{r}}$ casos, reduzidos para ${\displaystyle 2^{r-1}}$ casos saltando os complementos. Se ${\displaystyle f(x)}$ é redutível, o número de casos reduz-se ainda mais, retirando os ${\displaystyle f_{i}(x)}$ que aparecem num fator verdadeiro já encontrado. O algoritmo de Zassenhaus processa cada caso (cada subconjunto) rapidamente, no entanto, no pior caso, ele considera um número exponencial de casos.

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 de base de reticulado Lenstra–Lenstra–Lovász (LLL).^[6]

Uma versão simplificada do algoritmo de fatoração LLL é a seguinte: calcule uma raiz complexa (ou p-ádica) α do polinômio ${\displaystyle f(x)}$ com alta precisão e, em seguida, use o algoritmo de redução de base de reticulado Lenstra–Lenstra–Lovász para encontrar uma relação linear aproximada entre 1, α, α², α³, ... com coeficientes inteiros, que pode ser uma relação linear exata e um fator polinomial de ${\displaystyle f(x)}$. Pode-se determinar um limite para a precisão que garanta 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 matriz tem uma dimensão alta e entradas enormes, o que torna o cálculo lento.

A complexidade exponencial no algoritmo de Zassenhaus vem de um problema combinatório: como selecionar os subconjuntos certos de ${\displaystyle f_{1}(x),\ldots ,f_{r}(x)}$. As implementações de fatoração modernas funcionam de maneira semelhante a Zassenhaus, exceto que o problema combinatório é traduzido em um problema de reticulado que é então resolvido por LLL.^[7] Nesta abordagem, o LLL não é usado para computar coeficientes de fatores, mas sim para computar vetores com ${\displaystyle r}$ entradas em {0,1} que codificam os subconjuntos de ${\displaystyle f_{1}(x),\ldots ,f_{r}(x)}$ correspondentes aos verdadeiros fatores irredutíveis.

Podemos fatorar um polinômio ${\displaystyle p(x)\in K[x]}$, onde o corpo ${\displaystyle K}$ é uma extensão finita de ${\displaystyle \mathbb {Q} }$. Primeiro, usando a fatoração livre de quadrados, podemos supor que o polinômio seja livre de quadrados. Em seguida, definimos o anel quociente ${\displaystyle L=K[x]/p(x)}$ de grau ${\displaystyle n=[L:\mathbb {Q} ]=\deg p(x)\,[K:\mathbb {Q} ]}$; isto não é um corpo a menos que ${\displaystyle p(x)}$ seja irredutível, mas é um anel reduzido uma vez que ${\displaystyle p(x)}$ é livre de quadrados. De fato, se

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

for a fatoração desejada de p(x), o anel decompõe-se unicamente em corpos como:

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

Encontraremos esta decomposição sem conhecer a fatoração. Primeiro, escrevemos L explicitamente como uma álgebra sobre ${\displaystyle \mathbb {Q} }$: escolhemos um elemento aleatório ${\displaystyle \alpha \in L}$, que gera ${\displaystyle L}$ sobre ${\displaystyle \mathbb {Q} }$ com alta probabilidade pelo teorema do elemento primitivo. Se for este o caso, podemos calcular o polinômio mínimo ${\displaystyle q(y)\in \mathbb {Q} [y]}$ de ${\displaystyle \alpha }$ sobre ${\displaystyle \mathbb {Q} }$, encontrando uma relação ${\displaystyle \mathbb {Q} }$-linear entre 1, α, ... , αⁿ. Usando um algoritmo de fatoração para polinômios racionais, fatoramos em polinômios irredutíveis em ${\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 ${\displaystyle \alpha }$ corresponde a ${\displaystyle y\leftrightarrow (y,y,\ldots ,y)}$. Isso deve ser isomorfo à decomposição anterior de ${\displaystyle L}$.

Os geradores de L são x juntamente com os geradores de ${\displaystyle K}$ sobre ${\displaystyle \mathbb {Q} }$; escrevendo-os como polinômios em ${\displaystyle \alpha }$, podemos determinar os mergulhos de ${\displaystyle x}$ e ${\displaystyle K}$ em cada componente ${\displaystyle \mathbb {Q} [y]/q_{i}(y)=K[x]/p_{i}(x)}$. Encontrando o polinômio mínimo de ${\displaystyle x}$ em ${\displaystyle \mathbb {Q} [y]/q_{i}(y)}$, calculamos ${\displaystyle p_{i}(x)}$ e assim fatoramos ${\displaystyle p(x)}$ sobre ${\displaystyle K.}$

Em geral, a maioria dos polinômios não tem raízes quadradas. No entanto, algumas aplicações, como a função de engenheiros elétricos para a obtenção dos parâmetros Y de uma impedância do ponto de acionamento de uma rede de duas portas,^[8] utilizam polinômios quadrados que devem ser fatorados em dois polinômios de raiz quadrada idênticos. O algoritmo abaixo irá fatorar um polinômio quadrado, ${\displaystyle {\sqrt {x^{6}-6x^{5}+17x^{4}-36x^{3}+52x^{2}+48x+36}}}$, em duas raízes polinomiais idênticas, ${\displaystyle R=X^{3}-3x^{2}+4x-6}$, usando um exemplo do Mathematics Stack Exchange.^[9][10]

${\displaystyle {\begin{aligned}&{\begin{array}{|l|l|l|}\hline Q&R&R(2Q+R)\\\hline \\0&x^{3}&x^{6}\\\hline \\x^{3}&-3x^{2}&6x^{5}-9x^{4}\\\hline \\x^{3}-3x^{2}&4x&8x^{4}-24x^{3}+16x^{2}\\\hline \\x^{3}-3x^{2}+4x&-6&-12x^{3}+36x^{2}-48x+36\\\hline \end{array}}&{\begin{array}{|c|c|c|c|c|c|c|c|}\hline R&x^{3}&&-3x^{2}&&4x&&-6\\\hline 1&x^{6}&-6x^{5}&17x^{4}&-36x^{3}&52x^{2}&48x&36\\&x^{6}&&&&&&\\\hline 2&&-6x^{5}&17x^{4}&&&&\\&&-6x^{5}&9x^{4}&&&&\\\hline 3&&&8x^{4}&-36x^{3}&52x^{2}&&\\&&&8x^{4}&-24x^{3}&16x^{2}&&\\\hline 4&&&&-12x^{3}&36x^{2}&-48x&36\\&&&&-12x^{3}&36x^{2}&-48x&36\\\hline \end{array}}\end{aligned}}}$

Passos:

Passo 1: Calcule a raiz quadrada do termo principal, ${\displaystyle x^{6}}$, e coloque-o, ${\displaystyle x^{3}}$, no termo principal da linha de solução do polinômio R no topo e coloque o termo ${\displaystyle x^{6}}$ na linha 1 logo abaixo do polinômio a ser fatorado, como mostrado.

Passo 2: Subtraia o ${\displaystyle x^{6}}$ recém-colocado do polinômio a ser fatorado e baixe os dois termos seguintes para a linha 2.

Passo 3: Duplique o estado atual da solução do polinômio R, adicione um novo termo, Q, de modo que R(2Q+R) negue o termo principal da linha 2, e coloque o negativo de R(2Q+R) no espaço inferior da linha 2.

Passo 4: Subtraia os dois números da linha 2, coloque o resultado na linha 3 e traga para baixo os próximos dois termos da linha 1 para a linha 3.

Passo 5: Repita para todas as linhas e colunas restantes até completar.

Quando concluído, a solução do polinômio R aparecerá na coluna R da tabela do lado esquerdo e na linha R da tabela do lado direito.