計算機数学 (2020) 第15回

今回は、前回から説明している同時因子分離分解の中で、係数体が奇標数の場合に、ある条件下で無作為に与えられた多項式が分離多項式になる確率に関する補題を証明しました。

その後、係数体が偶標数の場合に成り立つ同様の補題を証明し、同時因子分離分解のアルゴリズムを提示した上で、計算量の見積もりを行いました。

今学期の授業内容はここまでです。今学期は、1変数多項式の最大公約子 (GCD) 計算と、有限体上の1変数多項式の因数分解のアルゴリズムを紹介しました。この話は、一意分解整域上の1変数多項式の因数分解へとつながっていくわけですが、この辺の話題はまた機会がありましたら別の授業などで触れることにしたいと思います。

計算機数学 (2020) 第14回

今回から、有限体上の1変数多項式の因数分解を行うもう一つの手法として、因子次数分離分解 (Distinct Degree Factorization) と同次因子分離分解 (Equal Degree Factorization) を組み合わせたアルゴリズムの解説に入りました。

今回は、因子次数分離分解の手法を説明し、同次因子分離分解の中で、係数体が奇標数の場合に、ある条件下で無作為に与えられた多項式が分離多項式になる確率に関する補題を紹介するところまで進みました。

次回（最終回）は、今回提示した補題の証明を行い、引き続いて係数体が偶標数の場合の分離多項式の探索について紹介します。