Na matemática e na álgebra computacional, a fatoração de polinômios ou fatoração polinomial expressa um polinômio com coeficientes em um determinado corpo ou nos inteiros como o produto de fatores irredutíveis com coeficientes no mesmo domínio. A fatoração de polinômios é um dos componentes fundamentais dos sistemas de álgebra computacional.
O primeiro algoritmo de fatoração polinomial foi publicado por Theodor von Schubert em 1793.FT Schubert: De Inventione Divisorum Nova Acta Academiae Scientiarum Petropolitanae v.11, pp. 172–182(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 esse tópico não é mais antiga que a década de 1960 e os primeiros sistemas de álgebra computacional:Kaltofen (1982) Quando os algoritmos de etapas finitas há muito conhecidos foram colocados pela primeira vez em computadores, eles se mostraram altamente ineficientes. O fato de que quase qualquer polinômio uni ou multivariado de grau 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 com que sucesso esse problema foi atacado durante os últimos quinze anos. (Erich Kaltofen, 1982)
Algoritmos e computadores modernos podem fatorar rapidamente polinômios univariados de grau superior a 1000 com coeficientes de milhares de dígitos. Um exemplo de grau 2401, levando 7,35 segundos, é encontrado na Seção 4 em: Hart, van Hoeij, Novocin: Practical Polynomial Factoring in Polynomial Time ISSAC'2011 Proceedings, pp. 163–170 (2011). Para esse propósito, mesmo para fatoração sobre os números racionais e corpos de números, uma etapa fundamental é a fatoração de um polinômio sobre um corpo finito.
Formulação da questão
Anéis de polinômios sobre os inteiros ou sobre um corpo são domínios de fatoração única. Isso significa que cada elemento desses anéis é o produto de uma constante e um produto de polinômios irredutíveis (aqueles que não são o produto de dois polinômios não constantes). Além disso, essa decomposição é única a menos da multiplicação dos fatores por constantes invertíveis.
A fatoração depende do corpo base. Por exemplo, o teorema fundamental da álgebra, que afirma que todo polinômio com coeficientes complexos tem raízes complexas, implica que um polinômio com coeficientes inteiros pode ser fatorado (com algoritmos de busca de raízes) em fatores lineares sobre o corpo complexo C. Da mesma forma, sobre o corpo dos 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 corpo dos racionais Q.
A questão da fatoração polinomial só faz sentido para coeficientes em um corpo computável cujo cada elemento pode ser representado em um computador e para o qual existem algoritmos para as operações aritméticas. No entanto, essa não é uma condição suficiente: Fröhlich e Shepherdson dão exemplos de tais corpos para os quais nenhum algoritmo de fatoração pode existir.
Os corpos de coeficientes para os quais algoritmos de fatoração são conhecidos incluem corpos primos (ou seja, o corpo dos números racionais e os corpos dos inteiros módulo um número primo) e suas extensões de corpo finitamente geradas. Coeficientes inteiros também são tratáveis. O método clássico de Kronecker é interessante apenas de um ponto de vista histórico; os algoritmos modernos procedem por uma sucessão de: Fatoração livre de quadrados Fatoração sobre corpos finitos e reduções: Do caso multivariado para o caso univariado. De coeficientes em uma extensão puramente transcendental para o caso multivariado sobre o corpo base (veja abaixo). De coeficientes em uma extensão algébrica para coeficientes no corpo base (veja abaixo). De coeficientes racionais para coeficientes inteiros (veja abaixo). De coeficientes inteiros para coeficientes em um corpo primo com p elementos, para um p bem escolhido (veja abaixo).
Fatoração parte primitiva-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)", é, a menos de seu sinal, o máximo 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 a menos do sinal do conteúdo. É uma convenção usual escolher o sinal do conteúdo de forma que o coeficiente principal da parte primitiva seja positivo.
Por exemplo,
é uma fatoração em conteúdo e parte primitiva.
Todo polinômio q com coeficientes racionais pode ser escrito
onde p ∈ Z[X] e c ∈ Z: é suficiente tomar para c um múltiplo de todos os denominadores dos coeficientes de q (por exemplo, seu produto) e p = cq. O conteúdo de q é definido como:
e a parte primitiva de q é a de p. Como para os polinômios com coeficientes inteiros, isso define uma fatoração em um número racional e um polinômio primitivo com coeficientes inteiros. Essa fatoração também é única a menos da escolha de um sinal.
Por exemplo,
é 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 MDC de inteiros reduz a fatoração de um polinômio sobre os racionais à fatoração de um polinômio primitivo com coeficientes inteiros, e a fatoração sobre os inteiros à fatoração de um inteiro e um polinômio primitivo.
Tudo o que precede permanece verdadeiro se Z for substituído por um anel de polinômios sobre um corpo F e Q for substituído por um corpo de funções racionais sobre F nas mesmas variáveis, com a única diferença de que "a menos de um sinal" deve ser substituído por "a menos da multiplicação por uma constante invertível em F". Isso reduz a fatoração sobre uma extensão de corpo puramente transcendental de F à fatoração de polinômios multivariados sobre F.
Fatoração livre de quadrados
Se dois ou mais fatores de um polinômio são idênticos, então o polinômio é um múltiplo do quadrado desse fator. O fator múltiplo também é um fator da derivada formal do polinômio (em relação a qualquer uma das variáveis, se houver várias).
Para polinômios univariados, fatores múltiplos são equivalentes a raízes múltiplas (sobre um corpo de extensão adequado). Para polinômios univariados sobre os racionais (ou mais geralmente sobre um corpo de característica zero), 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 um múltiplo de um quadrado, realizando uma sequência de cálculos de MDC começando com mdc(f(x), f '(x)). Para fatorar o polinômio inicial, basta fatorar cada fator livre de quadrados. A fatoração livre de 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 de polinômios.
No caso de um polinômio sobre um corpo finito, o algoritmo de Yun se aplica apenas se o grau for menor que a característica, porque, de outra forma, a derivada de um polinômio não nulo pode ser zero (sobre o corpo com p elementos, a derivada de um polinômio em xp é sempre zero). No entanto, uma sucessão de cálculos de MDC, partindo do polinômio e de sua derivada, permite calcular a decomposição livre de quadrados.
Métodos clássicos Esta seção descreve os métodos dos livros didáticos que podem ser convenientes ao calcular manualmente. Esses métodos não são usados para cálculos de máquina porque usam fatoração de inteiros, que atualmente é mais lenta que a fatoração polinomial.
Os dois métodos a seguir partem de um polinômio univariado com coeficientes inteiros para encontrar fatores que também são polinômios com coeficientes inteiros.
Obtendo fatores lineares
Todos os fatores lineares com coeficientes racionais podem ser encontrados usando o teste das raízes racionais. Se o polinômio a ser fatorado é , então todos os possíveis fatores lineares 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 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.
Método de Kronecker
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 é um polinômio com coeficientes inteiros, então é um inteiro assim que é um inteiro. Existe apenas um número finito de possíveis valores inteiros para um fator de . Portanto, se é um fator de o valor de deve ser um dos fatores de
Se procurarmos todos os fatores de um dado grau , podemos considerar valores, para , que dão um número finito de possibilidades para a tupla Cada tem um número finito de divisores , e cada -tupla onde a entrada é um divisor de , isto é, uma tupla da forma , produz um polinômio único de grau no máximo , 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 e cada tem finitamente muitos divisores, existem finitamente muitas dessas tuplas. Assim, uma busca exaustiva permite encontrar todos os fatores de grau no máximo .
Por exemplo, considere
.
Se este polinômio for fatorado sobre Z, então pelo menos um de seus fatores deve ser de grau dois ou menor, então é singularmente determinado 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
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 como possíveis fatores de . Testá-los exaustivamente revela que
construído a partir de (g(0), g(1), g(−1)) = (1,3,1) fatora .
Dividindo f(x) por p(x) dá o outro fator , de modo que . 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) é:Van der Waerden, Sections 5.4 and 5.6
Métodos modernos
Fatorando sobre corpos finitos