アルゴリズム論特論（塩田）　2017年度教材　第2回

  • 授業内容
    • てんびんクイズ
      • 問：十分大きな天秤と、a グラムと b グラムの分銅がたくさんあるとき、測ることのできる最小の重さはいくらか？
      • 予想：a と b の最大公約数

    • 最大公約数 gcd, 最小公倍数 lcm
      • a, b の任意の公倍数は lcm(a, b) の倍数
      • a, b の任意の公約数は gcd(a, b) の約数
      • gcd, lcm は「単なる大小関係」で定義したのに整除関係を導く

  • ツボ
    • 2つの自然数 a, b に対して次の2つの集合は一致する：
      • a x + b y ( x, y は整数 ) の形で書ける整数全体の集合
      • gcd(a, b) の倍数全体の集合

    • 特に、a, b を与えたとき、gcd(a, b) = a x + b y を満たす x, y が必ず存在する。

  • 次回予告
    • RSA暗号の設計には gcd や、上記の x が必要。
    • RSA暗号の安全性は素因数分解の困難さに基づいているので、素因数分解から gcd を求めることはできない。
    • 次回はその上手な方法を勉強します。

戻る