Factorización de polinomios módulo p

La calculadora encuentra factores polinómicos módulo p utilizando el algoritmo de Elwyn Berlekamp

Esta página existe gracias a los esfuerzos de las siguientes personas:

Anton

Juan Manuel Gimenez

Juan Manuel Gimenez

Creado: 2021-05-26 21:56:29, Última actualización: 2021-05-26 21:56:29

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.

PLANETCALC, Factorización polinómica de Berlekamp

Factorización polinómica de Berlekamp

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

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 1.

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 un
  • 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 (a0, a1 ... an-1) = 1,0...0
    • Inicializar la primera fila de la matrix Q (q0,0, q0,1 ... q0,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 = an-1
        • Bucle en j = n-1 .. 0 hacer lo siguiente
          • aj=aj-1-t*uj, suponiendo que a-1 = 0
      • Establecer la fila i de la matriz Q en el vector A
      • Restar 1 al elemento qi,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: c0 = c1 = .. = cn-1 = -1
    • Establecer r = 0
    • Bucle en k = 0 ... n-1 hacer lo siguiente
      • Bucle en j = 0 ... n-1 hacer lo siguiente
        • si qk,j ≠ 0 y cj<0
          • Establecer a = qk,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 qk,i
        • si no (si qk,j=0 o cj 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:
            • ak,s, si se encuentra el elemento s del vector C, como cs = 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 wi = 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 wi con los factores encontrados por gcd(v[j]-s,wi) ≠ 1 por cada s = 0 ... p


  1. D.Knuth The Art of Computer Programming vol 2, par. 4.6.2 Factorization of Polynomials 

URL copiada al portapapeles
PLANETCALC, Factorización de polinomios módulo p

Comentarios