Polynomial factorization
The calculator finds all factors of a polynomial with rational coefficients
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.
Rational polynomial factorization procedure^{1}
 Convert input polynomial in Q[x] to primitive polynomial in Z[x]
 Find all square factors using Yun squarefree factorization algorithm
 For each squarefree 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_{n}y
 If leading coefficient is not equal to 1 then transform it to monic one using formula:

 Find irreducible factors of v(y)=v_{1}v_{2}...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 CantorZassenhaus algorithm^{2}


 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)
 Determine upper limit of target factors coefficients by formula:



 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
 Invert monic polynomial transformation using formula:
URL copied to clipboard
Comments