Polynomial factorization

The calculator finds all factors of a polynomial with rational coefficients

This page exists due to the efforts of the following people:

Anton

Timur

Timur

Created: 2019-08-28 20:54:38, Last updated: 2021-02-26 13:45:27

The calculator below finds all irreducible factors of a polynomial with rational coefficients. To better understand how it works, switch on the 'Show details' toggle and read the calculator's description.

PLANETCALC, Polynomial factorization with rational coefficients

Polynomial factorization with rational coefficients

Input polynomial
 
Solution
 
The file is very large. Browser slowdown may occur during loading and creation.
The file is very large. Browser slowdown may occur during loading and creation.

Rational polynomial factorization procedure1

  • Convert input polynomial in Q[x] to primitive polynomial in Z[x]
  • Find all square factors using Yun square-free factorization algorithm
  • For each square-free factor of degree greater than 1, do the following steps
    • If leading coefficient is not equal to 1 then transform it to monic one using formula:
      v = a_n^{n-1}u(y/a_n)=\sum_{i=0}^{n-1} a_n^{n-1-i}a_iy^i+y^n, where
      v(y) - transformed monic polynomial,
      u(x) - original polynomial,
      an - leading coefficient of u(x),
      x = any
    • Find irreducible factors of v(y)=v1v2...vr in finite field Fp[x]
      • Find minimal prime number which is not divisor of v(y) discriminant
    • Use Hensel lifting to raise the finite field order of the factorization to the upper limit
      • Determine upper limit of target factors coefficients by formula:
        B=2^n\sqrt{n+i}||v||, where
        ||v||=max({|a_n|,...,|a_0|}) - maximum absolute value of polynomial coefficients (polynomial height)
      • Perform hensel lifting k\geq \frac{ln(2B)}{ln(p)} times
    • Check the factors by division v(y)/vi in Z[x], remove invalid factors
    • Invert monic polynomial transformation using formula:
      u(x)=pp(v_1(a_nx))pp(v_2(a_nx))...pp(v_r(a_nx))
      pp - primitive part function, which removes a content form an input polynomial

  1. Joel S. Cohen, Computer Algebra and Symbolyc Computation: Mathematical Methods, par. 9. Polynomial Factorization 

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

URL copied to clipboard
PLANETCALC, Polynomial factorization

Comments