Polynomial factorization

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.

Polynomial factorization with rational coefficients

Polynomial coefficients

Show details

Calculate

Calculation precision

Exact

Rounded

Digits after the decimal point: 2

Input polynomial

 

Solution

 

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

Download 

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

Download 

 Link  Save  Widget

Rational polynomial factorization procedure¹

• 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:
    , where
    v(y) - transformed monic polynomial,
    u(x) - original polynomial,
    a_n - leading coefficient of u(x),
    x = a_ny
• • Find irreducible factors of v(y)=v₁v₂...v_r in finite field F_p[x]
• • • Find minimal prime number which is not divisor of v(y) discriminant
• • • If p is small, use Berlekamp algorithm to find v(y) factors, otherwise use Cantor-Zassenhaus algorithm²
• • 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:
      , where
      - maximum absolute value of polynomial coefficients (polynomial height)
• • • Perform hensel lifting times
• • Check the factors by division v(y)/v_i in Z[x], remove invalid factors
• • Invert monic polynomial transformation using formula:
    
    pp - primitive part function, which removes a content form an input polynomial