アルゴリズム論特論（塩田）第3回 (5) 今日のまとめ、デモプログラム
今日のまとめ
- RSA暗号の安全性は、大きな数の素因数分解が困難であることに基づいている。
- 最大公約数 $\gcd(a, b)$ や $a x + b y = 1$ を満たす $x$, $y$ はRSA暗号に必要だが、その計算に素因数分解を使う訳にはいかない。
- ユークリッドのアルゴリズム、拡張ユークリッドアルゴリズムという手がある。
- プリント
自宅学習の例
- Ex.10 を真似て $1357 x + 246 y=1$ を満たす $x$, $y$ を求めてみる。
デモ
$a$, $b$ の値を入力するか乱数を発生させて「答」のボタンを押せば答が表示されます。