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

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

授業内容
- 素因数分解がわかっているときの gcd, lcm
- ユークリッドのアルゴリズム
  - gcd のみ求めるアルゴリズム
  - gcd(a, b) = a x + b y を満たす x, y も求めるアルゴリズム

ツボ
- RSA暗号の計算には gcd や上記の x が必要。
- RSA暗号は素因数分解の困難さに基づくので、gcd を素因数分解で求めるのはナンセンス。
- そこでユークリッドのアルゴリズムが必要になる。

問題
- 下記の場合については gcd(a,b) = 1 であることがわかっている。ユークリッドのアルゴリズムを用いてそれぞれ a x + b y = 1 を満たす整数の組 (x, y) をひとつ求めよ。