Polynomial factorization

 

• consider polynomials with integer coefficients (it is simple to convert a polynomial with rational coefficients into a problem in this domain)

• factorization splits a given polynomial into the product of polynomials :

  
  
  

• a polynomial is "square free", i.e., it does not have a factor which is the second or higher power of a polynomial, if and only if , that is, there does not exist a polynomial other than the constant that divides the polynomial and its derivative

• if the polynomial is not "square free" then

  
  
  

  
  
  

  and

• Berlekamp algorithm for factorization of "square free" polynomials in one variable modulo a prime

• Berlekamp-Hensel algorithm for factorization of "square free" polynomials in one variable with integer coefficients

• Kronecker algorithm for factorization of polynomial in more variables

• these algorithms exhibit exponential complexity

• there exists algorithms with only polynomial complexity

• uses of factorization: solving of polynomial equations, integration of rational functions, etc.

• example

  
  
  

• other examples