Calculadora de factorización de polinomios


Importante: Para factorizar polinomios enteros, el módulo usado en la caja de entrada debe ser cero.

Los polinomios enteros en una variable son expresiones que incluyen una variable llamada x, números enteros y las operaciones de suma, resta y multiplicación.

Se pueden expresar mediante la forma: f(x) = f0 + f1x + f2x2 + ... + fnxn.

El número n es el grado del polinomio. El coeficiente fn es el coeficiente principal y el coeficiente f0 es el término independiente. Se pueden escribir como grado(f), cp(f) y ti(f) respectivamente.

Sean f(x) y g(x) dos polinomios tales que grado(f) ≥ grado(g). Podemos definir la suma, resta y multiplicación como sigue:

f(x) + g(x) = h(x) significa hi = fi + gi si i ≤ grado(g) y hi = fi en caso contrario.

f(x) − g(x) = h(x) significa hi = figi si i ≤ grado(g) y hi = fi en caso contrario.

g(x) − f(x) = h(x) significa hi = gifi si i ≤ grado(g) y hi = −fi en caso contrario.

f(x) ⁢ g(x) = h(x) significa hi = f0gi + f1gi − 1 + ... + fig0 si i ≤ grado(g), hi = fi − grado(g)ggrado(g) + fi + 1 − grado(g)ggrado(g) − 1 + ... + fig0 en caso contrario.

La factorización de polinomios enteros es el proceso que encuentra uno o más polinomios irreducibles cuyo producto es el polinomio original. Un polinomio irreducible no se puede expresar como un producto de dos o más polinomios enteros.

Ejemplo: x4 − 1 = (x2 + 1) ⁢ (x + 1) ⁢ (x − 1)

Se puede demostrar que cualquier polinomio entero se puede factorizar de una sola manera en polinomios irreducibles.

La multiplicación de polinomios módulo un número primo se puede realizar de la manera habitual multiplicando los diferentes términos del polinomio y luego sumando los coeficientes del mismo grado. Finalmente se reducen los coeficientes módulo ese primo.

Por ejemplo, el producto de 3x2 + 5x + 1 y 6x2 + 4x + 3 módulo 7 es 18x4 + (30+12)x3 + (9+20+6)x2 + (15+4)x + 3 módulo 7 que es igual a 4x4 + 5x + 3

Se puede demostrar que cualquier polinomio módulo un número primo se puede factorizar como el primer coeficiente y polinomios mónicos de una sola manera (los polinomios mónicos son aquellos que tienen el primer coeficiente igual a 1.)

También se puede demostrar que si no hay factores repetidos, el polinomio se puede factorizar módulo una potencia de ese primo de una sola forma.

Esta aplicación Javascript puede evaluar y factorizar expresiones polinómicas módulo un primo o una potencia de número primo. También puede evaluar y factorizar polinomios enteros ingresando el valor cero en la caja de entrada Módulo.

Utilice la caja superior para ingresar el polinomio y la inferior para ingresar el módulo, que debe ser un número entero mayor que 1 que sea un número primo o un primo elevado a alguna potencia. Es posible simplemente evaluar el polinomio, o bien evaluarlo y factorizarlo, apretando el botón correspondiente.

Ejemplo para polinomio entero: para factorizar x30 − 1, ingrese x^30-1 en la caja superior y cero en la inferior. Luego presione el botón Factorizar.

Ejemplo para polinomio módulo primo: copie cualquiera de las expresiones que figura abajo en la caja de texto superior y escriba el número 211 (un número primo) en la caja de texto inferior. Luego apriete el botón denominado "Factorizar".

  • 6x^8+x^5+3
  • 2*((x+6)*(x-5)+xx)^4+23x

Algunos dispositivos móviles no permiten ingresar el símbolo de exponenciación. En este caso se puede escribir dos asteriscos ** para el operador de exponenciación. De esta manera, las siguientes expresiones son equivalentes:

  • 6x**8+x**5+3
  • 2*((x+6)*(x-5)+xx)**4+23x

Escribiendo un punto (.), la aplicación lo reemplazará por "x^". Esto reduce notablemente el tiempo de ingreso de expresiones polinómicas en dispositivos móviles porque no hay necesidad de cambiar de teclado numérico a alfabético y viceversa para escribir polinomios sencillos.

Para el primer ejemplo sería:

  • 6.8+.5+3

La factorización de polinomios de grados muy elevados requiere mucho tiempo. Debido a esto, la aplicación acepta polinomios de grado no superior a 1000.

La opción "superíndice" se utiliza para ver los exponentes como superíndices (cuando la opción está marcada) o precedida por el símbolo de intercalación (^) (cuando la opción no está marcada). La primera opción sirve para ver la factorización en pantalla o para imprimirla. La segunda opción se utiliza cuando hay que copiar los datos a otra aplicación.

Se pueden ingresar expresiones que usan los siguientes operadores y paréntesis:

  • + para suma
  • - para resta
  • * para multiplicación
  • / para división entera
  • % para resto
  • ^ o ** para exponenciación

Para el módulo se pueden usar los operadores indicados arriba y además:

  • n!: factorial
  • p#: primorial (producto de todos los primos menores o iguales a p).
  • B(n): número probablemente primo anterior a n
  • F(n): número de Fibonacci Fn
  • L(n): número de Lucas Ln = Fn-1 + Fn+1
  • N(n): número probablemente primo posterior a n
  • P(n): particiones irrestrictas (cantidad de descomposiciones de n en sumas de números enteros sin tener en cuenta el orden).
  • Gcd(m,n): Máximo común divisor de estos dos números enteros o polinomios.
  • Der(m): Derivada del polinomio.
  • Modinv(m,n): inverso de m modulo n, sólo válido cuando gcd(m,n)=1.
  • Modpow(m,n,r): halla mn módulo r.

Puedes usar el prefijo 0x para números hexadecimales, por ejemplo 0x38 es igual a 56.

Polinomios módulo un número primo

La división de polinomios requiere varias divisiones modulares donde el divisor es el coeficiente principal del polinomio divisor.

Para calcular la división modular a / b (mod p), primero debemos hallar el inverso multiplicativo modular c. Este número tiene la propiedad bc ≡ 1 (mod p) y se puede hallar usando el algoritmo extendido de Euclides como se muestra a continuación:

función modInv(value, modulus)
{
  V1 ← 1; V3 ← value;
  U1 ← 0; U3 ← modulus;
  mientras V3 ≠ 0
  {
    QQ ← U3 / V3;
    T1 ← U1 − V1 * QQ;
    T3 ← U3 − V3 * QQ;
    U1 ← V1; U3 ← V3;
    V1 ← T1; V3 ← T3;
  }
  retornar U1;
}

la división es igual al producto ac (mod p).

Para minimizar la cantidad de divisiones modulares (que tardan mucho tiempo), podemos multiplicar todos los coeficientes de ambos polinomios (dividendo y divisor) por el inverso multiplicativo del coeficiente principal del polinomio divisor. De esta manera, dividiremos por un polinomio mónico, esto es, un polinomio cuyo término principal vale 1. Esto no cambiará el cociente, pero deberemos multiplicar el resto por el coeficiente principal del polinomio divisor.

Ejejmplo: realizar la división (3⁢x3 + 7⁢x2 + 5⁢x + 6) / (4⁢x2 + 3⁢x + 10) (mod 11):

Primero debemos hallar el inverso multiplicativo de 4 (mod 11), que es igual a 3, porque 4 × 3 = 12 ≡ 1 (mod 11). Multiplicando todos los coeficientes por 3 obtenemos:

(9⁢x3 + 10⁢x2 + 4⁢x + 7) / (x2 + 9⁢x + 8) (mod 11)

Dividiendo el coeficiente principal del polinomio dividendo por el coeficiente principal del polinomio divisor: 9⁢x3 / x2 ≡ 9⁢x (mod 11).

Ahora restamos el producto de lo que acabamos de hallar por el polinomio divisor del polinomio dividendo. Obtenemos:

9⁢x3 + 10⁢x2 + 4⁢x + 7 - 9⁢x(x2 + 9⁢x + 8) ≡ 6⁢x2 + 9⁢x + 7 (mod 11). Debemos observar que 10 − 9 × 9 ≡ 6 (mod 11) y 4 − 9 × 8 (mod 11) ≡ 9 (mod 11).

Dividiendo el coeficiente principal del polinomio resto que acabamos de hallar por el coeficiente principal del polinomio divisor: 6⁢x2 / x2 ≡ 6 (mod 11).

Ahora restamos el producto de lo que acabamos de hallar por el polinomio divisor del polinomio resto. Obtenemos:

(6⁢x2 + 9⁢x + 7) − 6⁢(x2 + 9⁢x + 8) ≡ 10x + 3 (mod 11). Debemos observar que 9 − 6 × 9 ≡ 10 (mod 11) y 7 − 6 × 8 ≡ 3 (mod 11).

El polinomio cociente es igual a 9⁢x + 6 y el polinomio resto es igual a 4⁢(10x + 3) ≡ 7 x + 1 (mod 11).

Polinomios enteros

La división se realiza de la misma manera que en la subsección anterior, con la diferencia que no hay inverso multiplicativo del coeficiente principal del polinomio divisor. Así que por cada iteración del algoritmo, se necesita una división. Si el polinomio divisor no es mónico, a veces no podremos hacer la división. Esto ocurre cuando el coeficiente principal del resto no es múltiplo del coeficiente principal del divisor.

El máximo común divisor de dos polinomios es el polinomio de mayor grado posible, que divide ambos polinomios.

Por ejemplo: mcd(x2 + 6⁢x + 5, 2⁢x2 + 13⁢x + 15) = x + 5

Polinomios módulo un número primo

El máximo común divisor se puede hallar mediante el algoritmo de Euclides como se muestra a continuación:

función mcdm(pol1, pol2, p)
{
  a ← pol1;
  b ← pol2;
  mientras b ≠ 0
    t ← b;
    b ← resto(a, b) (mod p);
    a ← t;
  retornar a;
}

Polinomios enteros

Se puede utilizar el algoritmo recién mostrado para hallar el mcd de dos polinomios enteros, pero los coeficientes de los polinomios intermedios crecen rápidamente, así que no es útil.

Existen dos métodos eficientes para hallar el mcd: el algoritmo de subresultantes y el modular. El último, inventado por William Brown, utiliza mcd de polinomios módulo un número primo, así que es mejor para nosotros.

función mcdp(pol1, pol2)
{
  c1 ← cont(pol1);
  c2 ← cont(pol2);
  c ← mcd(c1, c2);
  a ← pol1 / c1;
  b ← pol2 / c2;
  h ← mcd(cp(pol1), cp(pol2));
  d ← min(grado(pol1), grado(pol2));
  m ← 1;
  gm ← 0;
  repetir
  {
    hacer
    {
      hacer
      {
        p ← nextPrime();
      } mientras resto(m*h, p) = 0;
      r ← pol1 (mod p);
      s ← pol2 (mod p);
      gp ← gcdm(r, s, p);
      si grado(gp) = 0
      {
        Salida c; salir;
      }
    } mientras grado(gp) > d;
    gp ← (h mod p)/cp(gp) * gp;
    si grado(gp) < d
    {
      m ← 1;
      gm ← 0;
      d ← grado(gp);
    }
    h ← ACR([gp, p], [gm, m]);
    si h = gm
    {
      h ← h / cont(h);
      si resto(a, h) = 0 y resto(b, h) = 0
      {
        Salida c*h; salir;
      }
    }
    m ← p * m;
    gm ← h;
  }
}

El contenido de un polinomio es el máximo común divisor de todos los coeficientes de ese polinomio. Se expresa como cont(f) en el algoritmo que se acaba de mostrar.

Los coeficientes del resultado del algoritmo chino del resto (function ACR) calculado módulo mp, deben estar en el rango −mp/2 a mp/2.

En este algoritmo se calculan varios mcd de los polinomios de entrada módulo diferentes primos. Podemos observar que sus grados son mayores o iguales que el grado del polinomio mcd.

Podemos distinguir tres casos:

  • El grado del mcd modular es mayor que el grado del mcd modular anterior: descartamos el nuevo resultado porque tiene el grado incorrecto.
  • El grado del mcd modular el menor que el grado del mcd modular anterior: descartamos el viejo resultado porque tiene el grado incorrecto. Lo reemplazamos por el nuevo resultado.
  • Ambos grados son iguales: Unimos los coeficientes de ambos mcd usando el algoritmo chino del resto. Este algoritmo halla g (mod mp) dados gm (mod m) y gp (mod p).

El algoritmo continúa hasta que el polinomio calculado divide los dos polinomios de entrada.

El algoritmo de factorización se divide en cuatro etapas: factorization de factores repetidos, factorización de grados diferentes, factorización de grados iguales y elevación de los factores. Todos los pasos requieren polinomios mónicos, así que antes de comenzar, debemos multiplicar todos los coeficientes por el inverso multiplicativo del coeficiente principal del polinomio.

Factorization de factores repetidos

Los siguientes etapas no funcionan si hay factores repetidos, así que el primer paso consiste en factorizar el polinomio de manera que no haya factores repetidos.

La derivada del polinomio f(x) = f0 + f1x + f2x2 + ... + fnxn es f'(x) = f1 + 2⁢f2x + ... + nfnxn − 1

El algoritmo recursivo es:

función FFR(f)
{
  i ← 1; g ← f';
  si g ≠ 0
  {
    c ← mcd(f, g);
    w ← f / c;
    mientras w ≠ 1
    {
      y ← mcd(w, c); z ← w / y;
      Salida(zi); i ← i + 1;
      w ← y; c ← c / y;
    }
    si c ≠ 1
    {
      c ← c1/p;
      Salida(SFF(c)p);
    }
  }
  else
  {
    f ← f1/p;
    Salida(SFF(f)p);
  }
}

Debemos hacer las siguientes etapas por cada polinomio en la salida de este algoritmo.

Factorización de grados diferentes

Este es un método que usa el hecho que el producto de todos los polinomios mónicos irreducibles de grados que dividen d (mod p) es igual a xex donde e = pd.

función FGD(f, p)
{
  i ← 1;
  h ← f;
  j ← x;
  q ← 0;
  mientras grado(h) ≥ 2⁢i
  {
    j ← jp (mod h);
    g ← gcdm(h, j − x);
    si g ≠ 1
    {
      Salida(g, i);
      q ← 1;
      h ← h / g;
    }
  }
  si h ≠ 1
  {
    Salida(h, grado(h));
    q ← 1;
  }
  si q = 0
  {
    Salida(f, 1);
  }
}

Los pares que forman la salida de esta función son la entrada de la siguiente etapa. El primer elemento del par es un factor de f que es el producto de todos los factores cuyo grado está especificado en el segundo elemento del par.

Factorización de grados iguales

Este es un método probabilístico inventado por David Cantor y Hans Zassenhaus que encuentra todos los factores del mismo grado de la salida del algoritmo anterior:

función FGI(f, d, p)
{
  n ← grado(f);
  Asignar f a la lista de factores;
  mientras tamaño(list of factors) < n/d
  {
    h ← polinomio al azar con grado(h) < n;
    e ← (qd − 1) / 2;
    g ← he − 1 (mod f);
    por cada elemento u de la lista de factores
    {
      si grado(u) > d
      {
        j ← mcdm(g, u);
        si j ≠ 1 y j ≠ u
        {
          descartar u de la lista de factores;
          agregar j y u/j a la lista de factores;
        }
      }
    }
  }
  Salida lista de factores
}

Elevación de los factores

Una vez que hallamos todos los factores irreducibles del polinomio módulo p, podemos calcular el factor del polinomio módulo pn si no hay factores repetidos. El siguiente algoritmo puede elevar de módulo m a m2, así que podemos ejecutarlo varias veces hasta obtener el módulo deseado.

Entrada: f = g*h (mod m), s*g + t*h = 1 (mod m)

Salida: f = g'*h' (mod m2), s'*g' + t'*h' = 1 (mod m2) with grado(s') < grado(h'), grado(t') < grado(g')

Todos los cálculos que se muestran abajo se realizan mod m2.

  e ← f - g*h
  Calcular q, r tales que s*e = q*h + r
  g' ← g + t*e + q*g
  h' ← h + r

  e ← s*g' + t*h' − 1
  Calcular q, r tales que s*e = q*h + r
  s' ← s − r
  t' ← t − t*e − q*g'

Los valores iniciales de s y t se obtienen de g y h mediante el algoritmo extendido de Euclides.

Podemos usar la salida de la sección anterior para factorizar polinomios enteros.

Primero debemos dividir el polinomio por su contenido (el máximo común divisor de todos los coeficientes). El resultado es la parte principal, cuya notación es pp(f).

Para separar los factores repetidos, podemos factorizar recursivamente mcd(f, f') y f/mcd(f, f').

En este momento sabemos que no hay factores repetidos. Debemos hallar un número primo pequeño p para el que ese polinomio no tenga factores repetidos. Este número primo se puede encontar fácilmente verificando que mcd(f, f') ≡ 1 (mod p).

Luego debemos hallar una cota para los coeficientes de los factores. Podemos calcular la cota de Knuth-Cohen para los coeficientes de los polinomios factores de la siguiente manera:

Si el polinomio G divide F tenemos para todo j:

|Gj| ≤ binomial(n-1, j)*(Σi |Fi|2)1/2 + binomial(n − 1, j −1) * |Fm|

donde m es el grado de F y n es el grado de G. El máximo grado a considerar es n = ceil(m/2).

Una vez hallada la cota B,debemos calcular el menor valor de e tal que 2⁢B < pe.

Ahora factorizamos el polinomio mod pe que tiene r factores diferentes. Si r > 10, podemos probar otros valores de p, así minimizamos la cantidad de factores encontrados. La aplicación hace el intento con hasta 5 primos diferentes.

Ahora combinaremos los factores encontrados módulo pe para obtener los factores que sean polinomios enteros. Hay 2r combinaciones posibles, pero la mayoría puede ser eliminada rápidamente.

Sea la combinación de factores hallados f0, f1, ..., fs. Calculemos a ≡ cp(f) ⁢ ti(f0)⁢ ti(f1) ⁢ ... ⁢ti(fs) (mod pe) y b ≡ cp(f) ⁢ ti(f) (mod pe). En ambos casos los productos deben estar en el rango −pe/2 a pe/2. Si a no divide b, podemos descartar esa combinación.

Para las pocas combinaciones que quedan, calcularemos a ≡ lc (f) ⁢ f0f1 ⁢ ... ⁢ fs (mod pe). Otra vez, los coeficientes de este polinomio deben estar en el rango −pe/2 a pe/2. Calculemos b = gcdp(a, cp(f) ⁢ f). Si el grado de b es cero, descartaremos la combinación. En caso contrario, el polinomio b es un factor no trivial de f.

Puede bajar el código fuente del programa actual y del viejo applet de factorización de polinomios GitHub. El código fuente está escrito en lenguaje C, por lo que es necesario Emscripten para generar Javascript.

Escrito por Dario Alpern. Actualizado el 23 de abril de 2019.

Si encuentra algún error o tiene algún comentario, por favor llene el formulario.