Fatoração polinomial em um campo finito
A calculadora encontra fatores de um polinômio utilizando o algoritmo de Cantor-Zassenhaus
Este conteúdo é licenciado de acordo com a Licença Creative Commons de Atribuição/CompartilhaIgual 3.0 (Unported). Isso significa que você pode redistribuir ou modificar livremente este conteúdo sob as mesmas condições de licença e precisa atribuir ao autor original colocando um hyperlink para este trabalho no seu site. Além disto, favor não modificar qualquer referência ao trabalho original (caso houver) que estiverem contidas neste conteúdo.
Esta calculadora encontra fatores irredutíveis de um polinômio univariado no campo finito utilizando o algoritmo de Cantor-Zassenhaus. Inicialmente, ela realiza a Fatoração de grau distinto para encontrar fatores, que futuramente podem ser decompostos. Finalmente, caso seja necessário, ela aplica um algoritmo de fatoração de grau igual, que está descrito logo abaixo da calculadora.
Fatoração polinomial de Cantor-Zassenhaus em campo finito
Algoritmo de fatoração de Cantor-Zassenhaus
Este algoritmo geralmente possui melhores características para módulo grande do que similares ao Algoritmo de fatoração de Berlekamp.
- Verifique se o polinômio é livre de quadrados
- Encontre todos os fatores para graus distintos
- Aplique o algoritmo de decomposição de grau igual, descrito a seguir, para cada fator cujo grau seja maior do que o grau distinto obtido na etapa anterior
Algoritmo de fatoração de grau igual
// u(x) - Polinômio de entrada de grau rd
// que possui r fatores cada
// de grau d no campo Fp
// p - ordem ímpar de campos
// d - grau de fatores alvos
// r - número de fatores alvos
s⟵ { u }
loop enquanto o tamanho(s) for menor que r
h ⟵ polinômio aleatório
de grau menor que 2d
g ⟵ h^(p^d-1/2) -1 módulo u
para cada a em s faça
se o grau(a) for maior que d
e máximo divisor comum(g, a) ≠ 1
e máximo divisor comum(g, a) ≠ a então
remova a de s
adicione máximo divisor comum(g,a) em s
adicione a/máximo divisor comum(g,a) em s
finalizar se
finalizar ação
finalizar loop
resultado s
Comentários