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.
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
- Loop em k = 1..n-1 faça o seguinte
- 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
- se qk,j ≠ 0 e cj<0
- Loop em j = 0 ... n-1 faça o seguinte
- 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
-
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
Calculadoras similares
PLANETCALC, Módulo p de fatoração polinomial
Comentários