Loading article…
データ評価におけるランダム性テスト（またはランダム性のテスト）は、データ セットの分布を分析して、ランダム(パターンなし) として記述できるかどうかを確認するために使用されるテストです。一部のコンピューター シミュレーションと同様に、確率的モデリングでは、潜在的な入力データの期待されるランダム性は、ランダム性の正式なテストによって検証され、データがシミュレーション実行での使用に有効であることを示すことができます。場合によっては、いわゆる「データ内のラン」のように、データは明らかにランダムではないパターンを示します (たとえば、0 から 9 までのランダムな値を期待していたのに、「4 3 2 1 0 4 3 2 1...」となり、4 を超えることはめったにないなど)。選択したデータ セットがテストに合格しない場合は、パラメーターを変更するか、ランダム性のテストに合格する他のランダム化データを使用できます。
背景
ランダム性の問題は、哲学的および理論的な重要な問題です。ランダム性のテストは、データセットに認識可能なパターンがあるかどうかを判断するために使用できます。パターンがあると、データセットを生成したプロセスが著しく非ランダムであることを示します。ほとんどの場合、統計分析は、実際には、ランダム性のテストではなく、データの規則性を見つけることに重点を置いています。今日使用されている多くの「乱数ジェネレータ」はアルゴリズムによって定義されるため、実際には疑似乱数ジェネレータです。それらが生成するシーケンスは、疑似ランダムシーケンスと呼ばれます。これらのジェネレータは、十分にランダムなシーケンスを常に生成するわけではなく、パターンを含むシーケンスを生成することがあります。たとえば、悪名高いRANDUルーチンは、スペクトルテストを含む多くのランダム性テストで大幅に失敗します。
Stephen Wolfram は、Rule 30の出力に対してランダム性テストを使用して、乱数生成の可能性を調べましたが[1]、有効なキー サイズが実際のサイズよりはるかに小さく[2] 、カイ 2 乗テストでパフォーマンスが低いことが示されました[3]。 不適切な乱数ジェネレータを使用すると、統計的仮定に違反して実験の有効性が疑わしくなります。NIST 標準などの一般的な統計テスト手法がありますが、Yongge Wang は NIST 標準では不十分であることを示しました。 さらに、Yongge Wang [4] は、統計的距離ベースおよび反復対数法則ベースのテスト手法を設計しました。この手法を使用して、Yongge Wang と Tony Nicol [5
ランダム性の特定のテスト
実際に使用されている (疑似) 乱数ジェネレーターには、かなり少数の異なるタイプがあります。これらは乱数ジェネレーターのリストに記載されており、次のものが含まれます。
- 線形合同型ジェネレータと線形フィードバックシフトレジスタ
- 一般化フィボナッチジェネレータ
- 暗号ジェネレータ
- 二次合同法ジェネレータ
- セルオートマトンジェネレータ
- 擬似ランダムバイナリシーケンス
これらのさまざまなジェネレータは、受け入れられたテスト スイートに合格する成功度が異なります。広く使用されているいくつかのジェネレータは、多かれ少なかれテストに合格しませんが、他の「より優れた」ジェネレータや以前のジェネレータ (現在の一連のテストすべてに合格し、すでに存在していたという意味で) はほとんど無視されています。
バイナリシーケンスのランダム性を測る実用的な方法は数多くある。統計的検定、変換、複雑性、あるいはそれらの組み合わせに基づく方法などがある。広く知られ広く使われている検定法としては、Marsaglia が導入したDiehard Battery of Testsがある。これはL'Ecuyer と Simard によってTestU01スイートに拡張された。ランダム性を測定するためにアダマール変換を使用することはS. Kakによって提案され、Phillips、Yuen、Hopkins、Beth と Dai、Mund、Marsaglia、Zaman によってさらに発展させられた。[6]
これらのテストのいくつかは線形複雑性を持ち、ランダム性のスペクトル測定を提供します。T. Beth と ZD. Dai は、コルモゴロフ複雑性と線形複雑性は実質的に同じであると主張しましたが[7] 、 Y. Wang は後に彼らの主張が間違っていることを示しました[8] 。しかし、Wang はMartin-Löf ランダムシーケンスの場合、コルモゴロフ複雑性は本質的に線形複雑性と同じであることも実証しました。
これらの実用的なテストにより、文字列のランダム性を比較することができます。確率論的には、特定の長さの文字列はすべて同じランダム性を持ちます。ただし、異なる文字列には異なるコルモゴロフ複雑性があります。たとえば、次の 2 つの文字列を考えてみましょう。
- 文字列1:
0101010101010101010101010101010101010101010101010101010101010101 - 文字列2:
1100100001100001110111101110110011111010010000100101011110010110
文字列 1 は、「'01' の 32 回の繰り返し」という短い言語的記述が可能です。この記述は 22 文字で、いくつかの基底シーケンスから効率的に構築できます。[説明が必要]文字列 2 には、64 文字の文字列自体を書き留める以外に明白な単純な記述はなく、[説明が必要]比較的効率的な基底関数表現もありません。線形アダマール スペクトル テスト (アダマール変換を参照) を使用すると、これらのシーケンスの最初のシーケンスは、2 番目のシーケンスよりもランダム性が大幅に低いことがわかります。これは直感と一致します。
注目すべきソフトウェア実装
参照
注記
- ^ウルフラム 、スティーブン（2002）。『新しい科学』ウルフラムメディア社、pp.975-976。ISBN 978-1-57955-008-0。
- ^ Willi Meier、Othmar Staffelbach (1991)。「セルオートマトンによって生成された疑似ランダムシーケンスの分析」。暗号学の進歩 - EUROCRYPT '91。コンピュータサイエンスの講義ノート。第 547 巻。pp. 186–199。doi : 10.1007/3-540-46416-6_17。ISBN 978-3-540-54620-7。
- ^ Moshe Sipper、Marco Tomassini (1996)、「セルラープログラミングによる並列乱数ジェネレーターの生成」、International Journal of Modern Physics C、7 (2): 181–190、Bibcode :1996IJMPC...7..181S、CiteSeerX 10.1.1.21.870、doi :10.1142/S012918319600017X 。
- ^ Yongge Wang. (疑似) 乱数ジェネレータの LIL テストの設計といくつかの実験結果について、http://webpages.uncc.edu/yonwang/、2014
- ^ Yongge Wang、Tony Nicol (2014)、「疑似ランダムシーケンスの統計的特性と PHP および Debian OpenSSL を使用した実験」、Esorics 2014、LNCS 8712 : 454–471
- ^ Terry Ritter、「ランダム性テスト：文献調査」、ウェブページ：CBR-rand。
- ^ Beth, T. および ZD. Dai. 1989. 疑似ランダムシーケンスの複雑さについて -- または: シーケンスを記述できる場合、それはランダムではない。暗号学の進歩 - EUROCRYPT '89。533-543。Springer-Verlag
- ^ Yongge Wang 1999. 線形複雑性と疑似ランダム性: Beth と Dai の結果について。Proc. Asiacrypt 99、288-298 ページ。LNCS 1716、Springer Verlag
- ^ ENT: 疑似乱数列テストプログラム、Fourmilab、2008年。
- ^ 暗号化アプリケーションのための乱数および疑似乱数ジェネレータの統計テストスイート、特別出版 800-22 改訂 1a、アメリカ国立標準技術研究所、2010 年。
- ^ NIST統計テストスイートの実装
外部リンク
- NISTの暗号ツールキットに含まれるランダム性テスト
- George Marsaglia、Wai Wan Tsang (2002)、「合格困難なランダム性テスト」、Journal of Statistical Software、第 7 巻、第 3 号
- DieHarder: 乱数テストスイート、Robert G. Brown、デューク大学
- CAcert.org のオンライン乱数ジェネレータ分析