Módulo p de fatoração polinomial

Esta calculadora encontra fatores irredutíveis de um determinado polinomial módulo p usando o algoritmo de fatoração de Elwyn Berlekamp. A descrição do algoritmo está logo abaixo da calculadora.

Fatoração polinomial de Berlekamp

Coeficientes polinomiais inteiros

Módulo

Calcular

Polinômio de entrada

 

Solução

 

O arquivo é muito grande; pode ocorrer lentidão do navegador durante o carregamento e a criação.

Download 

 Link  Salvar  Widget

Algoritmo de fatoração de Berlekamp

O algoritmo descrito aqui é uma compilação compacta do algoritmo de fatoração descrito no TAOCP (A Arte da Programação de Computador) volume 2 por D.Knuth ¹.

Dados iniciais

• u(x) - polinômio de n graus, n>=2
• p - módulo de número primo

Etapas de preparação

• Verifique se o polinômio é mônico. Caso não seja, divida todos os coeficientes polinomiais pelo coeficiente de grau mais alto u_n
• Verifique se o polinômio é livre de quadrados usando Fatoração polinomial quadrada livre em campo finito
• Para cada fator polinomial livre de quadrados de grau 2 ou superior, execute o algoritmo abaixo

O algoritmo

• Encontre a matriz Q (n * n ), onde n é um grau polinomial pelo procedimento abaixo:
  • Inicialize um vetor A (a₀, a₁ ... a_n-1) = 1,0...0
  • Inicialize a primeira linha da matriz Q (q_0,0, q_0,1 ... q_0,n-1) com 0,0...0
  • Loop em i = 1..n-1 faça o seguinte
    • Loop em k = 1..n-1 faça o seguinte
      • Defina t = a_n-1
      • Loop em j = n-1 .. 0 faça o seguinte
        • a_j=a_j-1-t*u_j, suponha que a_-1 = 0
    • Defina a linha i da matriz Q para o vetor A
    • Subtraia 1 do elemento q_i,i da matriz Q
• Encontre v^[1] ... v^[r] vetores linearmente independentes, como v^[1] Q = v^[2] Q = ... v^[r] Q = (0,0...0)
  • Defina todos os elementos do vetor C de n-elemento como -1 : c₀ = c₁ = .. = c_{n-1 = -1}
  • Defina r = 0
  • Loop em k = 0 ... n-1 faça o seguinte
    • Loop em j = 0 ... n-1 faça o seguinte
      • se q_k,j ≠ 0 e c_j<0
        • Defina a = q_k,j
        • Multiplique a coluna j da matriz Q por -1/a
        • Adicione uma coluna à outra (i ≠ j) coluna j multiplicada por q_k,i
      • caso contrário (se q_k,j=0 ou c_j igual a 0 ou maior que 0)
        • Defina r = r + 1
        • Defina cada elemento i de um novo vetor de n elementos v^[r] para um dos três seguintes:
          • a_k,s, se for encontrado o elemento s do vetor C, como c_s = i
          • 1, se i = k
          • 0 - caso contrário
• Encontre r fatores do polinômio u(x) utilizando os vetores v^[2] ... v^[r]
  • Encontre todos os w_i = gcd(u(x),v^[2]-s) ≠ 1 para cada s = 0 ... p
  • se a contagem de w < r faça o seguinte
  • Loop em j=3 ... r até a contagem de w < r
    • Substitua w_i pelos fatores encontrados pelo MDC (v^[j]-s,w_i) ≠ 1 para cada s = 0 ... p