Kroneckerův algoritmus pro faktorizeci polynomu v jedné proměnné

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

• pro každé celé číslo x_i platí
  
  $$a(x_i)=\prod_{j=1}^n a_j(x_i).$$
  
  

• na této rovnosti je založen Kroneckerův algoritmus pro nalezení faktorů polynomu v 1 proměnné s celočíselnými koeficienty:

  vstup: polynom a(x) stupně d >=1
  výstup: faktor polynomu a(x)
  
  for s=2,3,..,[d/2]+1 do
    1. vyber s různých celých čísel x1,...,xs
    2. if existuje xi takové, že a(xi)=0 then return (x - xi)
         else urči množinu E všech s-tic celých čísel
  	    (d1,d2,...,ds) takových, že každé di dělí a(xi)
    3. pro každou s-tici (d1,d2,...,ds) z E spočítej polynom gd(x) stupně s-1
       s celočíselnými koeficienty takový, že gd(xi)=di pro
       i=1,2,...,s;
       if gd(x) dělí a(x) then return gd(x)
  

• opakovaným použitím dostaneme úplnou faktorizaci

• existuje příliš mnoho kombinací dělitelů - algoritmus je neefektivní

• používá se modulární Berlekampův-Henselův algoritmus