アルゴリズム論特論(塩田) 2016年度教材 第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 を求めることはできない。
- 次回はその上手な方法を勉強します。
戻る