計算機数学 (2020) 第8回

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

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