計算機数学 (2020) 第4回

今回は、一意分解整域上の1変数多項式環における擬除算の定義から入りました。擬除算の定義を行い、Euclid互除法の除算を擬除算に置き換えることで、一意分解整域上の1変数多項式環でも最大公約因子 (GCD) を計算できるというものです。

後半では、多項式剰余列の定義を行いました。擬除算による多項式剰余列の計算の際、係数膨張が発生することを指摘し、対応策の一つとして、擬剰余を計算するたびに原始的部分 (primitive part) を計算することによる係数膨張の回避を紹介しました。この手法では、原始的部分の計算に係数部のGCD計算が必要になりますが、これを回避する方法として、部分終結式を用いる手法などがあります。

次回は、拡張Euclid互除法から進みます。