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 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
- If leading coefficient is not equal to 1 then transform it to monic one using formula:
-
- 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
-
-
-
- If p is small, use Berlekamp algorithm to find v(y) factors, otherwise use Cantor-Zassenhaus algorithm2
-
-
- 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)/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
- Invert monic polynomial transformation using formula:
URL zum Clipboard kopiert
Ähnliche Rechner
PLANETCALC, Polynomial factorization
Kommentare