Největší společný dělitel polynomů s celočíselnými koeficienty

• nyní uvažujeme polynomy z Z[x] v jedné proměnné x s celočíselnými koeficienty

• pseudo-dělení polynomů a(x), b(x) , pro které deg(a(x)) >= deg(b(x)) je definováno pomocí
  
  $${\rm lcof}(b(x))^{m-n+1}a(x)=pquot(a(x),b(x)) b(x)+prem(a(x),b(x))$$
  
  

• kde m=deg(a(x)), n=deg(b(x)) a lcof(b(x)) je vedoucí koeficient polynomu b(x) , tj. koeficient u n -té mocniny x , takže pseudo-podíl pquot(a(x),b(x)) a pseudo-zbytek prem(a(x),b(x)) jsou také ze Z[x]

• přitom 0 <= deg(prem(a(x),b(x))) < deg(b(x))

• polynom a(x) je primitivní pokud všechny jeho koeficienty jsou navzájem nesoudělné
  
  $$a(x)={\rm cont}(a(x)) \: {\rm pp}(a(x))$$
  
  

• cont(a(x)) je největší společný dělitel všech koeficientů polynomu a pp(a(x)) je primitivní část polynomu a

• Euclidův algoritmus posloupnosti polynomiálních zbytků (polynomial reminder sequence)

• Algoritmus

        gcd:=GCDPRS(a(x),b(x))
          [předpokládá, že stupeň polynomu a je větší nebo roven stupni
           polynomu b, tj. deg(a) >= deg(b)
           použité algoritmy:
             prem(a,b) - pseudo-zbytek po dělení polynomu a polynomem b
             pp(a)     - primitivní část polynomu a
             gcdi(j,k) - největší společný dělitel dvou celých čísel ]
        1. A:=pp(a);
           B:=pp(b);
        2. while not B =0 do
             r:=prem(A,B);
             A:=B;
             B:=r;
           od;
        3. gcd:=gcdi(cont(a),cont(b)) pp(A);
  

• koeficienty a mezivýsledky rostou velice rychle, neefektivní algoritmus

• je možné na každém kroku počítat primitivní část zbytku a pokračovat ve výpočtu s primitivní částí; výpočet primitivní části však vyžaduje výpočet největších společných dělitelů koeficientů, celých čísel, který je pro velká čísla časově náročný

• modulární přístup; výpočty prováděny modulo prvočíslo p

  • aplikovat homomorfismus na koeficienty

  • spočítat největší společný dělitel transformovaných polynomů modulo p

  • použít Čínský zbytkový algoritmus pro rekonstrukci koeficientů v největším společném děliteli