homechevron_rightStudychevron_rightMathchevron_rightAlgebrachevron_rightPolynomials

# Polynomial factorization

The calculator finds all factors of a polynomial with rational coefficients

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

Input polynomial

Solution

## 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 finite field order of the factorization to 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