Fatoração polinomial em um campo finito
A calculadora encontra fatores de um polinômio utilizando o algoritmo de Cantor-Zassenhaus
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
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.
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 sURL copiado para a área de transferência
Calculadoras similares
PLANETCALC, Fatoração polinomial em um campo finito
Comentários