アルゴリズム論特論（塩田）　2014年度教材

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

前回の復習
- exercise02.pdf
授業内容
- 2つの整数 a, b の最大公約数を gcd(a,b) と表す。
  - gcd(a,b) ≧ 0 に取る。
  - b=0 のときは gcd(a,0) = abs(a)
  - gcd(0,0) = 0
- ax+by の形で表される整数全体の集合は、gcd(a,b) の倍数全体の集合に等しい。
ツボ
- a と b が互いに素であれば、ax+by=1 を満たす x, y が存在する。
- この x は RSA 暗号の復号化処理に必要である。