乱数

Random number

現代の多くのコンピュータは決定論で動作するので、外部のエントロピー(ランダム事象)を取り込まない限り、真の乱数を作り出すことができない。乱数のように見えるが計算で得られるものは、どこまで行っても一定の法則に従って生成される疑似乱数となる。

疑似乱数(Pseudo random number)に対して、外部のエントロピーを利用した乱数を暗号学的疑似乱数(Cryptographically secure pseudo random number)と呼んだりする。

(一般の)疑似乱数の特徴

再現性がある。乱数の種(初期値)を同じにすれば、シミュレーションなどで繰り返し同じ結果が得られる。

早い。計算のみで乱数を作り出すので、外部のエントロピーの取り込みに伴う速度の低下がない。

暗号学的疑似乱数の特徴

再現性がない。暗号のような用途では望ましい。

遅い。エントロピーが必要なため、乱数を出力しすぎるとエントロピーが枯渇してしまう。

疑似乱数の具体的な実装例

乱数についての検討

真の乱数

各項の数値に値域と乱数分布以外の一切の規則性がない数列

情報量はその数列以下にならない。(数列の一部から、別の部分の数列の予測ができない。)

一応ルールに従い圧縮もできるが、別の所に情報量を付け替えているだけ。

一様乱数(一様分布に従う乱数)の場合

数列の次の数はすべて等確率で現れる。

一度ある数が現れたら、その数はしばらく現れない、というような挙動にはならない。(実はこれが意外と難しい)

数字を桁で表現して、桁の一部分を取っても、それは一様分布である。

たくさんサンプルを取ると、大数の法則に従う。(ミクロでは偏りがあっても、マクロでは偏りがない。)

真の乱数と考えられるもの

量子力学

今の所、完全にランダムに見える。

ただし、本当にランダム(一切何の法則にも従っていない)なのかどうかは分からない。

観測(=相互作用)自体がランダム事象を引き起こしてしまうため。

その他の事象を完全に取り除くことができないため。

観測自体に測定限界があるため。

真の乱数に近いもの

熱力学的な挙動

これはミクロでは静的な物理法則(非量子力学)に基づいているが、あまりに要素が多いためにランダムに見える。

より大きな情報量の中から一部の小さな情報量を取り出しているのでランダムに見える。

カオスによる挙動

疑似乱数の大多数はカオスに基づいている。単純な法則で動作するが、複雑化するために一見ランダムに見える。

関連