homechevron_rightStudychevron_rightMathchevron_rightAlgebrachevron_rightPolynomials

# Polynomial factorization

The calculator finds all factors of a polynomial with rational coefficients This content is licensed under Creative Commons Attribution/Share-Alike License 3.0 (Unported). That means you may freely redistribute or modify this content under the same license conditions and must attribute the original author by placing a hyperlink from your site to this work https://planetcalc.com/8373/. Also, please do not modify any references to the original work (if any) contained in this content.

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:
, 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:
, where
- maximum absolute value of polynomial coefficients (polynomial height)
• Perform hensel lifting times
• Check the factors by division v(y)/vi in Z[x], remove invalid factors
• Invert monic polynomial transformation using formula:

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