数理科学IIB（第3回）

今回は、まず、前回最後に証明したHenselの補題に基づき、Hensel構成の基本的なアルゴリズムについて説明ました。次に、Hensel構成の最初の段階の因子が共通因子を持つとHensel構成が適用できない「共通因子問題 」を紹介し、共通因子問題の回避策を紹介しました。最後に、共通因子問題への回避策を含め、Hensel構成を用いたGCD計算のアルゴリズムを提示、説明しました。

次回は、中国剰余定理を用いたGCD計算のアルゴリズムの紹介から始めます。