Módulo p de fatoração polinomial

A calculadora encontra fatores polinomiais módulo p utilizando o algoritmo de Elwyn Berlekamp

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.

PLANETCALC, Fatoração polinomial de Berlekamp

Fatoração polinomial de Berlekamp

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

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 1.

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 un
  • 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 (a0, a1 ... an-1) = 1,0...0
    • Inicialize a primeira linha da matriz Q (q0,0, q0,1 ... q0,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 = an-1
        • Loop em j = n-1 .. 0 faça o seguinte
          • aj=aj-1-t*uj, suponha que a-1 = 0
      • Defina a linha i da matriz Q para o vetor A
      • Subtraia 1 do elemento qi,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 : c0 = c1 = .. = cn-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 qk,j ≠ 0 e cj<0
          • Defina a = qk,j
          • Multiplique a coluna j da matriz Q por -1/a
          • Adicione uma coluna à outra (i ≠ j) coluna j multiplicada por qk,i
        • caso contrário (se qk,j=0 ou cj 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:
            • ak,s, se for encontrado o elemento s do vetor C, como cs = 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 wi = 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 wi pelos fatores encontrados pelo MDC (v[j]-s,wi) ≠ 1 para cada s = 0 ... p


  1. D.Knuth The Art of Computer Programming (A Arte da Programação de Computador) vol. 2, parágrafo. 4.6.2 Factorization of Polynomials (Fatoração de polinômios) 

URL copiado para a área de transferência
PLANETCALC, Módulo p de fatoração polinomial

Comentários