アルゴリズム論特論（塩田）第3回 (1) はじめに
はじめに
前回、ふたつの整数 $a$, $b$ の最大公約数 $\gcd(a,b)$ に対して
$\gcd(a,b)=ax+by$
を満たす $x$, $y$ が存在することを示しました。
RSA暗号をはじめとする公開鍵暗号の設計には、
$2048$ ビット程度の整数 $a$, $b$ に対して $\gcd(a,b)$ やこの $x$, $y$ を計算する必要があります。
しかし、
- RSA暗号は大きな数の素因数分解問題が困難であることに基づく暗号ですから、
最大公約数の計算に $a$, $b$ の素因数分解を仮定してはいけません。
- $ax+by=\gcd(a,b)$ を満たす $x$, $y$ も、前回の授業で存在することだけはわかりましたが、
単純な検索で求めることは不可能です。
これらの計算を高速に実現できる「ユークリッドのアルゴリズム」を今日は勉強します。
宇宙の年齢
問 宇宙の年齢はおよそ何秒と言われているか？
答え
およそ 138億年 ≒ $4.35 \times 10^{17}$ 秒。
問 地球から観測可能な宇宙にある原子の個数はおよそ何個と言われているか？
問 $2048$ ビットの整数は10進数でおよそ何桁か？
答え
$2^{10} = 1024 \mbox{ ≒ } 10^3$ ゆえ、およそ $600$ 桁。( $2048 \times \log_{10} 2= 616.509\cdots$ )
$2048$ ビットの整数が如何に大きいかイメージできますか？
このサイズの検索範囲に対して全検索を掛けるような計算は、如何に性能の高い計算機を用いても宇宙が終わるまでに答えを得ることができません。
ここ極めて大事!!