疑似乱数
ちょっとした思いつき。
疑似乱数列を生成する計算方法の妥当性を調べるのにチューリングテスト的方法は使えるか。
放射線などを用いた真の乱数列と、調査したい計算方法の生成する疑似乱数列とが、二つのチャネルA, Bから流れ出てくる。でもどちらの数列がどちらのチャネルから流れてくるかは分からないとする。乱数を検定するアルゴリズムを別途用意しておき、二つのチャネルのどちらが真の乱数列であるか判定できるか。 ――という話題。
それができるなら、ランダムネスと知能との類似性という逆説的で面白い話題につながるね。
チューリングテストでは、本物の人間と適切な判定者によって、コンピュータのプログラムの知能性(?)を判定する(言い換えるとそれを知能の定義とする)。上に書いたテストでは、真の乱数列(本物の人間の代わり)と検定をするアルゴリズム(適切な判定者の代わり)によって、 疑似乱数列の計算方法の妥当性を判定する(言い換えるとそれを乱数の定義とする)。
※ すでに誰かが考えていそうな話だけれど、結城はこれ以上展開できないので、念のため公開(上で書いたことは、すごく当たり前かすごくナンセンスかのどちらかのような気もする)。
|・σ・)ノ(暗号学的な)疑似乱数の定義
まさに結城さんが考えているような定義そのもの.
暗号の方だとこんな感じ.
伸長関数を考えて, ある決定性アルゴリズムGが疑似乱数生成器*1であるとは, で, 任意の多項式時間確率的アルゴリズムAについて, がnについて無視できること (ただし, はそれぞれ長さn, l(n)の一様分布に従う確率変数. 確率はとAのコインによる).
追記: 数式の読み方
Gの出力と真の乱数列を見分ける多項式時間アルゴリズムが存在しなければ, Gは疑似乱数生成器.
Aが見分けるとは, Aに真の乱数を突っ込んだときの出力の分布と, AにGの出力を突っ込んだときの出力の分布との統計的な差がnegligibleでないこと.
セッティングはこんな感じ. 伸長関数なんで, 1^nは突っ込まなくても良かったはず.
(画像はPowerpoint 2007 Betaで作成. willustratorを使おうかと思ったが, 矢印が無いので困る.)
今来たビットと前までのビットに関連性を見つけられないという定義との同値性はYaoが示していた(筈)ので, 扱いやすい上の定義が使われている.
ChaitinやKolomogorov流の乱数の定義は計算できない数列のことなので, 違うな. 出来た数列を真の乱数列と比較するのではなく, その列を生成出来る有限の長さのプログラムがあるかどうか (ある意味では圧縮できるかどうか) で定義している.
疑似乱数列を生成するという話には使いづらい.
さらに追記: 10/27
統計的な疑似乱数と暗号学的な疑似乱数は全然性質が違うので注意.
上二つで話されているのは, 統計的な疑似乱数の方の話.
もう一つ. 暗号学的な疑似乱数の定義では, 攻撃者Aが決定性多項式時間アルゴリズムGの中身を知っていても良い.
したがって, 統計的な疑似乱数としてよく使われる線形性を持つ疑似乱数生成器は暗号学的な疑似乱数にはなり得ない.
*1:Pseudorandom Number Generator, PRGとかPRNG