計算機数学 (2020) 第11回

今回から、有限体上の1変数多項式の因数分解に入りました。今回は、Berlekamp（バールカンプ）の因数分解アルゴリズムのうち、f-簡約多項式の存在性に関する議論を行いました。

次回は f-簡約多項式の存在性に関する議論の続きを行ったのち、f-簡約多項式の計算方法の説明に進みます。

計算機数学 (2020) 第10回

今回は、標数0の一意分解整域上の1変数多項式の無平方分解に関する性質について述べ、無平方分解のアルゴリズムと計算量を概観しました。その後、有限体上の1変数無平方分解のアルゴリズムを紹介しました。

次回から、有限体上の1変数多項式の因数分解のアルゴリズムの話題に入る予定です。

計算機数学 (2020) 第9回

今回は、前半で、モジュラー法のもう一つの方法として、中国剰余定理 (Chinese Remainder Theorem) に基づく1変数多項式の最大公約式 (GCD) 計算のアルゴリズムを紹介しました。

後半では、1変数多項式の無平方分解の話題に入り、無平方の定義に触れたのち、標数0の一意分解整域上の無平方分解に関する基本的な性質について述べました。

次回は、今回の続きの説明を行ったのち、標数0の一意分解整域上の1変数多項式の無平方分解、ついで有限体上の1変数多項式の無平方分解のアルゴリズムを紹介します。

計算機数学 (2020) 第8回

今回は、Henselの補題の証明の最後の部分を説明し、Hensel構成の計算量の見積もりを行いました。その後、Hensel構成を持ちいたGCD計算の際に遭遇しうる「共通因子問題」と、その回避策を紹介しました。

次回は中国剰余定理に基づくGCD計算のアルゴリズムの紹介から始める予定です。