Fatoração polinomial

A calculadora encontra todos os fatores de um polinômio com coeficientes racionais

A calculadora abaixo encontra todos os fatores irredutíveis de um polinômio com coeficientes racionais. Para entender melhor como ela funciona, ative o botão 'Mostrar detalhes' e leia a descrição da calculadora.

PLANETCALC, Fatoração de polinômios com coeficientes racionais

Fatoração de polinômios com coeficientes racionais

Polinômio de entrada
 
Solução
 
O arquivo é muito grande; pode ocorrer lentidão do navegador durante o carregamento e a criação.
O arquivo é muito grande; pode ocorrer lentidão do navegador durante o carregamento e a criação.

Procedimento de fatoração polinomial racional1

  • Converta o polinômio de entrada em Q[x] para polinômio primitivo em Z[x]
  • Encontre todos os fatores de quadrados utilizando Algoritmo de fatoração livre de quadrados de Yun
  • Para cada fator livre de quadrados de grau maior do que 1, siga as etapas a seguir
    • Se o coeficiente líder não for igual a 1, então transforme-o em mônico utilizando a fórmula:
      v = a_n^{n-1}u(y/a_n)=\sum_{i=0}^{n-1} a_n^{n-1-i}a_iy^i+y^n, onde
      v(y) - polinômio mônico transformado,
      u(x) - polinômio original,
      an - coeficiente líder de u(x),
      x = any
    • Encontre fatores irredutíveis de v(y)=v1v2...vr no campo finito Fp[x]
      • Encontre o número primo mínimo que não seja divisor do discriminante de v(y)
    • Utilize o lema de Hensel para elevar a ordem do campo finito da fatoração para o limite superior
      • Determine o limite superior dos coeficientes dos fatores alvos através da fórmula:
        B=2^n\sqrt{n+i}||v||, onde
        ||v||=max({|a_n|,...,|a_0|}) - valor absoluto máximo dos coeficientes polinomiais (altura do polinômio)
      • Execute o lema de Hensel k\geq \frac{ln(2B)}{ln(p)} vezes
    • Verifique os fatores por divisão v(y)/vi em Z[x], remova os fatores inválidos
    • Inverta a transformação polinomial mônica usando a fórmula:
      u(x)=pp(v_1(a_nx))pp(v_2(a_nx))...pp(v_r(a_nx))
      pp - função de parte primitiva, que remove um conteúdo de um polinômio de entrada

  1. Joel S. Cohen, Álgebra Computacional e Computação Simbólica: Métodos Matemáticos, par. 9. Fatoração Polinomial 

  2. Donald Knuth, The Art of Computer Programming (A Arte da Programação de Computador) vol.2, par. 4.6.2 Fatoração de Polinômios 

URL copiado para a área de transferência
PLANETCALC, Fatoração polinomial

Comentários