-
自然界を観察すると、
-
いたるところに
ランダムな揺らぎがある。
-
「ノイズ」というランダムな揺らぎを
-
計測することで、完全にランダムな数列を得られる。
-
ノイズを抽出（計測）することで、
-
数列を得るのだ。
-
例えば、
-
TVのノイズの電流をずっと計測すると、
-
完全にランダムな数列が作られる。
-
ランダムな数列を視覚化するには
-
軌道を描き、その方向を
-
数字によって変えれば良い。
-
これを「ランダム・ウォーク」という。
-
数列のどの範囲にも、どの部分にも
-
規則が現れないことに注目しよう。
-
次の動きは絶対に予測できないのだ。
-
ランダムな過程は
あらかじめ予測できないので、
-
「非決定的」と呼ばれる。
-
一方で、機械は「決定的」だ。
-
その動作は予測でき、繰り返しになる。
-
1946年、ジョン・フォン・ノイマン は
-
コンピュータを軍事目的に使おうとしていた。
-
特に水素爆弾の設計に関わっていた。
-
ENIAC というコンピュータを用い、
-
核融合の方法に関する計算を
-
何度も行おうとした。
-
しかし、そのためには
-
繰り返しのあるランダムな数列に
-
必要なだけ素早くアクセスする必要があった。
-
しかし ENIAC の内部メモリは
ひどく限られていたので、
-
長いランダム数列を記憶することができなかった。
-
そこで ノイマンは、次の方法で
-
ランダムのゴチャゴチャ具合を
-
機械で再現するアルゴリズムを開発した：
-
まず「シード」と呼ばれる
完全にランダムな数字を選択する。
-
この数字は ノイズの計測や、
-
現在時刻のミリ秒によって決める。
-
次に この数字を計算機に入力し、
簡単な処理をする。
-
シードを 2乗 して、
-
結果の まんなか を出力する。
-
出力は次のシードとして用いられる。
-
これを 必要な回数だけ繰り返す。
-
これが「平方採中法」だ。
-
乱数生成の方法は、
-
他にも沢山ある。
-
数列のランダムさは、
-
初期シードのみに依存する。
-
シードが同じなら、数列は同じ。
-
さて、完全なランダムと
-
擬似ランダムの違いは何だろう。
-
各 数列を ランダム・ウォーク で表してみよう。
-
似たように見えるが、スピードを上げると？
-
擬似ランダムは 結局 繰り返しになる。
-
これはアルゴリズムが
以前と同じシード値を
-
生成すると発生し、
-
そこから 周期的になる。
-
擬似ランダムが繰り返しになるまでの
数列の長さをー
-
「ピリオド」という。
-
ピリオドは初期シードの桁数に強く制限される。
-
例えば 2桁のシードを用いると、
-
アルゴリズムが 同じシードを生成し、
繰り返しになるまで
-
多くて 100通り の数字を生成できる。
-
3桁のシードなら、
繰り返しまでの数を
-
1000通りに拡大できる。
-
4桁のシードなら、
繰り返しまでの数字の個数は
-
1万まで広がる。
-
しかし もしシードが十分に大きければ、
-
繰り返しまで 数兆、数京もの数列を
-
生成できる。
-
しかしキーの違いには注意が必要だ。
-
擬似ランダム数を生成する時、
-
起こり得る数列はかなり制限される。
-
例えば、
-
アリスが完全ランダムで
20個のシフト数を生成したとする。
-
これは あり得るシフト数列が書かれた、
-
均一な紙の山から
1枚を選ぶのに等しい。
-
この山には 26^20 ものページがあるから、
-
天文学的な大きさになる。
-
山の元に立って、光を上に向けて放つと、
-
頂上にいる人間が光を目にするのは
-
2億年先になる。
-
これと比べて、アリスが 20桁の擬似ランダム数列を、
-
4桁のシードで生成した場合は、
-
10,000 通りの初期シードから
-
1つを選ぶに等しい。
-
つまり 彼女が生成できる数列は 10,000 通りしかなく、
-
全数列のうちの
ごく小さな １部分にすぎない。
-
シフト数をランダムから擬似ランダムに置き換えた時、
-
鍵空間を ごくごく小さな シード空間にまで
縮めることになる。
-
だから 擬似ランダムをー
-
完全なランダムのように見せかけるには、
-
コンピュータが 全てのシードを試みるのを
-
現実的に不可能にする必要がある。
-
ここで 情報工学の世界では、
次の2つがハッキリと区別される。
-
「可能」と
-
「現実的な時間内で可能」 の違い。
-
例えるなら、自転車のダイヤル鍵と同じ理屈だ。
-
全ての番号を試せば、
誰でも簡単に解除の番号が分かると
-
知られている。
-
しかし それには何日も掛かるので、
-
8時間くらいなら、事実上 安全と考えられる。
-
擬似ランダムの生成では、
-
シードの桁数が増えるほど
強固なセキュリティになる。
-
最も速いコンピュータが
-
全てのシードを試すまでに 何百年も掛かるのなら、
-
完璧に強固ではなくても、
事実上 安全とみなして
-
差し支えない。
-
コンピュータが速くなるのに従い、
-
シードの大きさを増やす必要がある。
-
擬似ランダムのお陰で、
アリスとボブは
-
前もって全てのランダムシフト数を
共有しなくてよくなった。
-
代わりに、それより短いランダムなシードを共有し、
-
ランダムに見える数列を
必要な時に 生成すれば
-
よい。
-
しかし もし、
-
彼らが二度と会えず、シードを共有できなくなったら
どうなるだろう？
