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.

PLANETCALC, Fatoração polinomial de Cantor-Zassenhaus em campo finito

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 s
URL copiado para a área de transferência
PLANETCALC, Fatoração polinomial em um campo finito

Comentários