Factorización de polinomios módulo p

Esta calculadora encuentra factores irreducibles de un polinomio dado módulo p utilizando el algoritmo de factorización de Elwyn Berlekamp. La descripción del algoritmo está justo debajo de la calculadora.

Factorización polinómica de Berlekamp

Coeficientes de polinomios enteros

Módulo

Calcular

Polinomio de entrada

 

Solución

 

El archivo es muy grande; La ralentización del navegador puede ocurrir durante la carga y creación.

Descargar 

 Enlace  Guardar  Widget

Algoritmo de factorización de Berlekamp

El algoritmo descrito aquí es una compilación compacta del algoritmo de factorización descrito en TAOCP vol 2 por D.Knuth ¹.

Datos iniciales

• u(x) - polinomio de grado n, n>=2
• p - módulo del número primo

Pasos de preparación

• Compruebe que el polinomio es mónico. Si no lo es, divida todos los coeficientes del polinomio por el coeficiente de mayor grado u_n
• Compruebe que es un polinomio sin radicales usando la factorización de polinomios sin radicales en campo finito
• Para cada factorización de polinomios sin radicales de grado 2 o superior, ejecute el algoritmo siguiente

El algoritmo

• Hallar la matriz Q (n * n ), donde n es un grado del polinomio por el procedimiento siguiente:
  • Inicializar un vector A (a₀, a₁ ... a_n-1) = 1,0...0
  • Inicializar la primera fila de la matrix Q (q_0,0, q_0,1 ... q_0,n-1) con 0,0...0
  • Bucle en i = 1..n-1 hacer lo siguiente
    • Bucle en k = 1..n-1 hacer lo siguiente
      • Establecer t = a_n-1
      • Bucle en j = n-1 .. 0 hacer lo siguiente
        • a_j=a_j-1-t*u_j, suponiendo que a_-1 = 0
    • Establecer la fila i de la matriz Q en el vector A
    • Restar 1 al elemento q_i,i de la matriz Q
• Encontrar v^[1] ... v^[r] vectores linealmente independientes, como v^[1] Q = v^[2] Q = ... v^[r] Q = (0,0...0)
  • Establecer todos los elementos del vector C de n elementos a -1: c₀ = c₁ = .. = c_{n-1 = -1}
  • Establecer r = 0
  • Bucle en k = 0 ... n-1 hacer lo siguiente
    • Bucle en j = 0 ... n-1 hacer lo siguiente
      • si q_k,j ≠ 0 y c_j<0
        • Establecer a = q_k,j
        • Multiplicar la columna j de la matriz Q por -1/a
        • Añadir a cada una de las otras columnas (i ≠ j) la columna j por q_k,i
      • si no (si q_k,j=0 o c_j igual a 0 o mayor que 0)
        • Establecer r = r + 1
        • Establecer cada elemento i de un nuevo vector v de n elementos^[r] a uno de los tres siguientes:
          • a_k,s, si se encuentra el elemento s del vector C, como c_s = i
          • 1, si i = k
          • 0 - en caso contrario
• Encontrar r factores del polinomio u(x) utilizando los vectores v^[2] ... v^[r]
  • Encontrar todos los w_i = gcd(u(x),v^[2]-s) ≠ 1 para cada s = 0 ... p
  • si la cuenta de w < r hacer lo siguiente
  • Bucle en j=3 ... r hasta que la cuenta de w < r
    • Reemplazar w_i con los factores encontrados por gcd(v^[j]-s,w_i) ≠ 1 por cada s = 0 ... p