PLANETCALC Online calculators

Login
StudyMathAlgebraPolynomials

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.

PLANETCALC, Polynomial factorization with rational coefficients

Polynomial factorization with rational coefficients

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

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

Similar calculators

 #factorization #math #polynomial Algebra factorization Math Polynomials rational
PLANETCALC, Polynomial factorization
Anton2021-02-26 13:45:27

Comments