Faktorizace polynomů

• uvažujeme polynomy s celočíselnými koeficienty

• faktorizace rozloží daný polynom a(x) na součin polynomů a_j(x)
  
  $$a(x)=\prod_{j=1}^n a_j(x)$$
  
  

• polynom a(x) je "square free", tj. nelze z něho vytknout žádnou druhou nebo vyšší mocninu polynomu, právě když gcd(a(x),a'(x))=c (konstanta), tj. polynom je nesoudělný se svojí derivací

• máme-li polynom a(x) , který není "square free"
  
  a(x)=b(x)² c(x)
  
  
  
  
  a'(x)=2b(x)b'(x)c(x)+b(x)²c'(x)
  
  
  potom gcd(a(x),a'(x))=b(x)d(x)

• platí, že gcd(a(x),a'(x))dělí a(x); na zájkadě této vlastnosti lze sestavit algoritmus pro rozklad polynomu na "square free" faktory

• Berlekampův algoritmus pro factorizaci "square free" polynomů v jedné proměnné modulo prvočíslo p

• Berlekampův-Henselův algoritmus pro faktorizaci "square free" polynomů v jedné proměnné v celočíselném oboru koeficientů

• Kroneckerův algoritmus pro faktorizaci polynomů ve více proměnných

• exponenciální složitost algoritmů

• existují algoritmy s polynomiální složitostí

• použití faktorizace - řešení polynomiálních rovnic, integrace racionálních funkcí, aj.

• příklad
  
  $$\begin{eqnarray*}8x^3y&+&40x^2y^4+2x^2y^2z+4x^2y\\ &+&4x^2z^2+10xy^5z+20xy^4+2... ...&+&xyz^3+2xz^2+5y^4z^3+10y^3z^2\\ &=&(2xy+z^2)(4x+yz+2)(x+5y^3) \end{eqnarray*}$$
  
  

• další příklady