乱数生成器で得られる出力は、偏りがないことが求められます。
この章では乱数を検証ツールに関して、紹介します。
単純な検証ツールと乱数検証テストスイートの二種類について述べます。
あらかじめの注意ですが、昨今の乱数検証テストスイートは、そのオーダとしてGBは当たり前、場合によってはTBのオーダの乱数列を対象とします。(NeuGの生成速度では、TBのオーダは現実的ではないでしょう。飛石技術でのNeuGのテストでは、10日間くらいかけて 64GB を得てテストしています。)
簡単に使えるツールにEntがあります。疑似乱数列のテスト(pseudorandom number sequence test)と名前がついていますが、もちろん、一般の乱数列の検証にも使えます。乱数列に対して一バイトあたりのエントロピーの値の概算や、モンテカルロ法で求めた円周率の値が得られるので、直感的にもわかりやすいでしょう(モンテカルロ法がいかに効率がよくないかもわかります)。
rng-toolsに付属のrngtestでは、FIPS 140-2 に基づいた一連のテストが行えます。
乱数検証テストスイートとしては、現在のところ、TestU01 がお勧めでしょう。解説の論文もあります[1]。そのウェブサイトでは、GPLv3+ の配布条件の自由ソフトウェアである、と著作権告示されています。(残念ながら、ソースコードの中の著作権告示は古いままでGPLv3+とは書かれていません。)
今後、期待されるのは、PractRand[2]です。コードはパブリック・ドメインとされています。その名のとおり、研究目的以上の実用を目指しているライブラリで、付属のテストも大変、強力です。まだ、バージョン0.90の時点ではコードの配布にソースコードだけでなくバイナリも含まれている、などの荒い点も残りますが、とても期待できるプロジェクトです。疑似乱数の実装の利用/勉強にもどうぞ。
すぐ使ってみる場合には、Dieharder[3]が便利かもしれません。Debian GNU/Linuxならばパッケージに入っていますから apt-get するだけで使えます。
この分野で長らく使われているのは NIST がソフトウェアを配布している sts 2.1.1 です。NIST Special Publication 800-22[4]で解説されています。この10年ほどでしょうか、乱数生成と言えばこのテストスイートで試してみる、となってました。そういった慣習が残っていますから、過去との比較の意味でテストする価値はあるでしょう。
しかし、このテストスイート自身は、現在では、どちらかというと歴史的なものです。今となっては、TestU01のような信頼できるテストスイートでは(必ずしも)ないかもしれません。また、PractRandのように最新の知見を取り込んでいたり効率良いテストを目指したものではないでしょう。
歴史的ということでは、George Marsaglia先生のDiehard Battery of Tests of Randomness[5]に触れないわけには行きますまい。Dieharderテストスイートの名前の由来にもなってます。
この分野を勉強したいという方には、Knuth先生の本[6]でしょう。当該の章の始まりの箴言が Von Neumann, 章の最後(Exercises の前)の箴言が、Marsagliaというのも面白いですね。
さらに勉強する方には[7]でしょう。
| [1] | TestU01:
|
| [2] | PractRand (Practically Random): |
| [3] | Dieharder: |
| [4] | NIST Special Publication 800-22:
|
| [5] | Diehard Battery of Tests of Randomness:
|
| [6] | Chapter 3 Random numbers:
|
| [7] | Chapter 5 Pseudorandom Bits and Sequences
|