🕳️ 💽 👨🏿‍💻 NISTメソッドによるバイナリシーケンスのランダム性の統計的検証 🧒 👴🏽 ✍🏼

何らかの方法で暗号化に遭遇した人は誰でも、乱数ジェネレーターがこれを実行できないことを知っています。たとえば、このようなジェネレーターの用途の1つは、キーの生成です。しかし、誰もが同時に考えるわけではありませんが、このジェネレーターがどれほど「良い」のかを考えています。そして考えてみると、これらの乱数が暗号化のこの分野にどの程度当てはまるかを評価する「公式」な基準は世界には一つもないという事実に直面しました。乱数のシーケンスが予測可能な場合、このシーケンスが使用される最も強力な暗号化アルゴリズムでも脆弱であることがわかります。たとえば、攻撃者が「クラック」できる情報を取得するために攻撃者が「ソート」する必要があるキーのスペースが大幅に減少します»システム全体。幸いなことに、さまざまな組織がここで物事を整理しようとしています。特に、米国規格協会NISTは一連の数字のランダム性を評価する一連のテストを開発しました。これらについては、この記事で説明します。しかし、最初に、少しの理論（私はそれが退屈ではないことを提示しようとします）。

ランダムバイナリシーケンス

第一に、乱数の生成とは、プログラマーの好みに関係なく、バイトではなくバイナリ文字0と1のシーケンスを取得することを意味します。理想的な同様のジェネレーターは、「理想的な」コイン（両側から同じ確率で落下する平らなコイン）を投げることです。これは必要な回数投げられますが、問題は理想的なものがなく、そのようなジェネレーターのパフォーマンスが残るより良い（1コイン成長= 1ビット）。それにもかかわらず、以下で説明するすべてのテストは、調査中の乱数ジェネレーターが仮想の理想コインにどれだけ「類似」または「似ていない」かを評価します（「ランダム」キャラクターを取得する速度ではなく、「品質」によって）。

第二に、すべての乱数ジェネレーターは、真にランダムな物理乱数ジェネレーター/センサー（DSPH / FDSCH）と擬似乱数-ソフトウェア乱数ジェネレーター/ジェネレーター（MAP）の2種類に分けられます。前者は入力としてランダムな無限プロセスを取り、出力は無限の（観測時間に応じて）シーケンス0と1を与えます。後者は開発者によって指定された決定論的な関数で、いわゆるその後、出力でシーケンス0と1が得られます。このグレインを知って、シーケンス全体を予測できます。優れたMAPとは、以前の値の履歴全体を粒子なしで保持して、後続の値を予測することが不可能なマップです。このプロパティは、直接予測不能と呼ばれます。逆の予測不可能性もあります-生成された値をいくつでも知っていると、穀物を計算できないことです。

最も簡単な方法は、真にランダム/物理的なDSPを使用し、予測可能性を考慮しないことです。ただし、問題があります。

基礎となるランダムな現象/プロセスは、正しい速度で数字を生成できない場合があります。 2048ビットキーのペアを最後に生成したことを思い出した場合、お世辞をしないでください。これはめったに起こりませんか？次に、1秒あたり数百のSSL接続要求を受け入れるサーバーを想像してください（SSLハンドシェイクには乱数のペアの生成が含まれます）。
見た目では、ランダム現象は見かけほどランダムではないかもしれません。たとえば、電磁ノイズは、いくつかの多かれ少なかれ均一な周期信号の重ね合わせである場合があります。

NISTが提供する各テストは、終了シーケンスを受け取ります。次に、特定のシーケンスの特定のプロパティを特徴付ける統計が計算されます。これは、単一の値または値のセットのいずれかです。その後、これらの統計は参照統計と比較され、完全にランダムなシーケンスが得られます。参照統計は数学的に導かれ、多くの定理と科学論文がこれに当てられています。記事の最後に、必要な数式が表示されるソースへのすべての参照が示されます。

ゼロおよび対立仮説

テストの基礎は帰無仮説の概念です。私はそれが何であるかを説明しようとします。何らかの統計情報を取得したとしましょう。たとえば、1000人のグループに含まれる肺がんの人の数とします。そして、このグループの一部の人々は喫煙者であり、他の人々はそうではないことを知っておいてください。次のタスクは、喫煙と病気の間に関係があるかどうかを理解することです。帰無仮説は、2つの事実間に関係がないという仮定です。この例では、これは喫煙が肺がんを引き起こさないという仮定です。また、帰無仮説に反論する対立仮説もあります。現象の間には関係があります（喫煙は肺がんを引き起こします）。乱数の項を渡すと、シーケンスが真にランダムであるという帰無仮説（その符号は互いに等しく独立して現れる）が仮定されます。したがって、帰無仮説が真の場合、ジェネレーターは十分に「良い」乱数を生成します。

仮説はどのようにテストされますか？一方では、実際に収集されたデータに基づいて（つまり、測定されたシーケンスに従って）統計が計算されます。一方、数学的な方法（理論的に計算）によって取得された参照統計があり、これは真にランダムなシーケンスになります。明らかに、収集された統計を参照と比較することはできません。ジェネレータがどれほど優れていても、まだ完全ではありません。そのため、5％などの特定のエラーが発生します。たとえば、収集された統計が基準から5％を超えて逸脱している場合、帰無仮説は信頼性が非常に高くないと結論付けられます。

仮説を扱っているため、イベントの開発には4つのオプションがあります。

シーケンスはランダムであるという結論が下され、これが正しい結論です。
シーケンスはランダムではないが、実際にはランダムであると結論付けられます。このようなエラーは、第1種のエラーと呼ばれます。
シーケンスはランダムとして認識されますが、実際にはそうではありません。このようなエラーは、第2種のエラーと呼ばれます。
正しく拒否されたシーケンス

第1種のエラーの確率は、 統計的有意性のレベルと呼ばれ、αで示されます。つまり αは、「良い」ランダムシーケンスを拒否する確率です。この値はアプリケーションによって決定されます。暗号化では、0.001から0.01のαを使用するのが一般的です。

各テストでは、いわゆる P値：これは、実験ジェネレーターが仮説の真のものより悪くないシーケンスを生成する確率です。 P値= 1の場合、シーケンスは完全にランダムであり、0の場合、シーケンスは完全に予測可能です。その後、P値がαと比較され、αより大きい場合、帰無仮説が受け入れられ、シーケンスはランダムとして認識されます。それ以外の場合、拒否されます。

テストでは、α= 0.01が使用されます。これにより、次のことがわかります。

P値が≥0.01の場合、シーケンスは99％の信頼レベルでランダムと見なされます
P値が<0.01の場合、シーケンスは99％の信頼レベルで拒否されます。

そのため、テストに直接渡します。

周波数ビットテスト

明らかに、シーケンスがランダムであるほど、この比率は1に近くなります。このテストでは、この比率が1にどれだけ近いかを評価します。

+1にはそれぞれ「1」、-1にはそれぞれ「0」を取り、シーケンス全体の量を考慮します。これは次のように書くことができます：

S _n = X ₁ + X ₂ + ... + X _n 、ここでX _i = 2x _i -1。

ところで、彼らは、一連の実験における「成功」の数の分布は、各実験で与えられた確率での成功または失敗が可能な場合、二項分布を持っていると言います。

次のシーケンスを取ります：1011010101

次に、S = 1 +（-1）+ 1 + 1 +（-1）+ 1 +（-1）+ 1 +（-1）+ 1 = 2

統計を計算します：

追加のエラー関数を使用してP値を計算します。

相補誤差関数は次のように定義されます。

結果が0.01より大きいことがわかります。これは、シーケンスがテストに合格したことを意味します。少なくとも100ビット長のシーケンスをテストすることをお勧めします。

周波数ブロックテスト

このテストは以前のテストに基づいて行われ、各ブロックの比率「1」/「0」のみがカイ二乗法で分析されます。この比率がほぼ1であることは明らかです。

たとえば、シーケンス0110011010を指定し、3ビットのブロックに分割します（最後の「所有者なし」0は破棄されます）。

011 001 101

各ブロックの比率πiを計算します：π1 = 2/3、π2 = 1/3、π3 = 1/3。次に、N自由度（ここでNはブロック数）を使用したカイ2乗法により統計を計算します。

特別な関数Qを使用してP値を計算します。

Qはいわゆる次のように定義された不完全な上ガンマ関数 ：

この場合、関数は標準のガンマ関数です。

P値が0.01より大きい場合、シーケンスはランダムと見なされます。少なくとも100ビット長のシーケンスを分析することをお勧めします。また、M> = 20、M> 0.01n、N <100の関係も満たす必要があります。

同一の連続ビットのテスト

テストでは、同一ビットのすべてのシーケンスが検索され、これらのシーケンスの数とサイズが真にランダムなシーケンスの数とサイズにどれだけ対応するかが分析されます。ポイントは、0から1への変更（またはその逆）が非常にまれである場合、そのようなシーケンスはランダムなシーケンスを「プルしない」ということです。

シーケンス1001101011を指定すると、まず、総質量の単位の割合を計算します。

次に、条件がチェックされます。

満たされていない場合、テスト全体が失敗したとみなされ、すべてが終了します。この例では、0.63246> 0.1です。これは、さらに先に進むことを意味します。

交番符号Vの総数を計算します。

どこで

もし

、または

そうでなければ。

エラー関数を使用してP値を計算します。

result> = 0.01（この例のように）の場合、シーケンスはランダムと見なされます。

ブロック内のユニットの最長シーケンスをテストします

nビットの初期シーケンスは、それぞれMビットのNブロックに分割されます。その後、各ブロックでユニットの最長シーケンスが検索され、その後、インジケーターが真のランダムシーケンスの同じインジケーターにどれだけ近いかが推定されます。ユニットが適切に分散されている場合、ゼロも適切に分散されるため、明らかにゼロの同様のテストは必要ありません。

ブロックの長さは？ NISTは、ブロックに分割する方法について、いくつかの参照値を推奨しています。

全長n	ブロック長、M
128	8
6272	128
750,000	10,000

シーケンスを与えてみましょう：

11001100 00010101 01101100 01001100 11100000 00000010

01001101 01010001 00010011 11010110 10000000 11010111

11001100 11100110 11011000 10110010

8ビットのブロックに分割し（M = 8）、その後、各ブロックのユニットの最大シーケンスを計算します。

ブロックする	ユニット長
11001100	2
00010101	1
01101100	2
01001100	2
11100000	3
00000010	1
01001101	2
01010001	1
00010011	2
11010110	2
10,000,000	1
11010111	3
11001100	2
11100110	3
11011000	2
10110010	2

次に、次の表に基づいて、さまざまな長さの統計を検討します。

v _i	M = 8	M = 128	M = 10000
v ₀	≤1	＆le4	＆LE10
v ₁	2	5	11
v ₂	3	6	12
v ₃	≥4	7	13
v ₄		8	14
v ₅		≥9	15
v ₆			≥16

この表の使用方法：M = 8であるため、対応する1列のみを確認します。 v _iを考慮します。

v ₀ = { 最大のブロック数。 長さ≤1 } = 4

v ₁ = { 最大のブロック数。 長さ= 2 } = 9

v ₂ = { 最大のブロック数。 長さ= 3 } = 3

v ₃ = { 最大のブロック数。 長さ≥4 } = 0

カイ2乗を計算します。

KとRの値がそのようなテーブルに基づいて取得される場合：

M	K	R
8	3	16
128	5	49
10,000	6	75

理論的確率πiは定数で与えられます。たとえば、K = 3およびM = 8の場合、π0 = 0.2148、π1 = 0.3672、π2 = 0.2305、π3 = 0.1875を取ることをお勧めします。（他のKおよびMの値は[2]に記載されています）。

次に、P値を計算します。

この例のように、0.01より大きい場合、シーケンスはかなりランダムと見なされます。

バイナリマトリックスランクテスト

このテストでは、元のシーケンスで構成される行列を分析します。つまり、元のバイナリシーケンスから構築された互いに素な部分行列のランクを計算します。このテストは、コバレンコの研究[6]に基づいており、科学者は0と1で構成されるランダム行列を調査しました。彼は、行列M x QがランクR（ここでR = 0,1,2、 ...分（M、Q）。これらの確率は次と等しいです：

NISTでは、M = Q = 32を使用することをお勧めします。また、シーケンスの長さはn = M ^ 2 * Nになります。しかし、たとえば、M = Q = 3を使用します。わずかな誤差で、式を単純化でき、これらの確率は等しくなります。

したがって、シーケンス01011001001010101101を指定すると、2つのマトリックスに十分な数のマトリックスに「分解」します。

行列のランクを決定します。R1 = 2、R ₂ = 3であることがわかります。テストには3つの数字が必要です。

F _M = { ランクM の行列の数 } = { ランク3の行列の数 } = 1
F _M-1 = 1（同様）
N-F _M -F _M-1 = 2-1-1 = 0

カイ2乗を計算します。

P値を計算します：

結果が0.01より大きい場合、シーケンスはランダムと見なされます。 NISTは、シーケンスの合計の長さを38MQ以上にすることを推奨しています。

スペクトルテスト

実験シーケンスは、周波数ピークを識別するためにスペクトル分解が行われる離散信号と見なされます。明らかに、そのようなピークは周期的な成分の存在を示しますが、これは腸ではありません。要するに、テストは95％の障壁を超えるピークを明らかにし、これらのピークの割合が5％を超えるかどうかを確認します。

ご想像のとおり、離散フーリエ変換を使用して、シーケンスを周期成分の合計として表します。次のようになります。

ここで、x _kは+1に対応する初期シーケンスであり、-1は-1に対応します。Xjは複素振幅の取得値です（複素とは、振幅と位相の実数値の両方を含むことを意味します）。

ここで周波数はどこですか？答えは、指数関数を三角関数で表現できるということです。

私たちのテストでは、興味深いのは位相ではなく、振幅の絶対値です。そして、これらの絶対値を計算すると、それらは対称的であることがわかります（これは、複雑な値から実際の値への移行におけるよく知られた事実です）。情報。

このすべてを例で示します。シーケンス1001010011を与えます。

次に、x = {1、-1、-1、1、1、-1、1、-1、-1、1、1}。

例えば、GNU Octaveプログラムでフーリエ分解を行う方法は次のとおりです。

octave:1> x = [1, -1, -1, 1, -1, 1, -1, -1, 1, 1] x = 1 -1 -1 1 -1 1 -1 -1 1 1 octave:2> abs(fft(x)) ans = 0.0000 2.0000 4.4721 2.0000 4.4721 2.0000 4.4721 2.0000 4.4721 2.0000

対称性が観察されることがわかります。したがって、0、2、4.4721、2、4.4721の5つの値で十分です。

次に、式によって境界値を計算します

これは、シーケンスが真にランダムな場合、ピークの95％がこの境界を超えてはならないことを意味します。

ピークの制限数を計算します。これはT未満である必要があります。

次に、分解の結果を見て、4つのピークすべてが境界値よりも小さいことを確認します。次に、この違いを評価します。

P値を計算します：

判明したのは0.01より大きいため、ランダム性の仮説が受け入れられます。はい、テストには少なくとも1000ビットを使用することをお勧めします。

重複しないパターンのテスト

実験シーケンスは、同じ長さのブロックに分割されます。例：

1010010010 1110010110

各ブロックで、たとえば「001」などのパターンを探します。 互いに素という言葉は、パターンがシーケンス内にある場合、次の比較では見つかったパターンのビットをキャプチャしないことを意味します。検索の結果、i番目のブロックごとに、見つかったケースの数に等しい数W _iが見つかります。

したがって、ブロックの場合、W ₁ = 2およびW ₂ = 1です。

101 001 001 0

111 001 0110

シーケンスが本当にランダムであるかのように、数学的期待値と分散を計算します。以下は公式です。ここで、N = 2（ブロック数）、M = 10（ブロック長）、m = 3（サンプル長）。

カイ2乗を計算します。

不完全なガンマ関数を介して最終的なP値を計算します。

P値が0.1より大きいことがわかります。これは、シーケンスがかなりランダムであることを意味します。

1つのテンプレートのみを評価しました。実際、パターンのすべての組み合わせをチェックする必要があり、さらに、これらのパターンのさまざまな長さについてもチェックする必要があります。どちらが必要かは特定の要件に基づいて決定されますが、通常は9または10が必要です。意味のある結果を得るには、N <100およびM> 0.01 * nを使用する必要があります。

交差する交差パターンのテスト

このテストは、テンプレートが見つかったときに、検索ウィンドウがテンプレートの長さではなく、1ビットだけシフトされるという点で、前のテストと異なります。記事を煩雑にしないために、この方法による計算の例を示しません。それは完全に似ています。

ユニバーサルマウアーテスト

このテストでは、シーケンス内のパターンの間隔を評価します。テストの意味は、シーケンスがどれだけ圧縮可能であるかを理解することです（もちろん、可逆圧縮を意味します）。シーケンスの圧縮率が高いほど、ランダム性は低くなります。このテストのアルゴリズムは、Habr形式では非常に扱いにくいため、省略します。

線形難易度テスト

このテストは、実験シーケンスが線形フィードバックシフトレジスタ（またはLFSR、線形フィードバックシフトレジスタ）から取得されたという仮定に基づいています。これは、無限シーケンスを取得するためのよく知られた方法です。ここでは、次の各ビットは、レジスタに「座っている」ビットの特定の関数として取得されます。 LFSRの欠点は、常に有限の期間があることです。シーケンスは必然的に遅かれ早かれ繰り返されます。 LFSRが長いほど、ランダムシーケンスは良くなります。

初期シーケンスは長さMの等しいブロックに分割されます。次に、各ブロックについて、Berlekamp – Masseyアルゴリズム[10]を使用して、その線形複雑度（L _i ）が検出されます。 LFSRの長さ。次に、見つかったすべてのL _iについて、6自由度のカイ2乗分布が推定されます。例を示します。

ブロック1101011110001（M = 13）が与えられ、Berlekamp-MasseyアルゴリズムがL = 4を与えたとします。これが正しいことを確認してください。実際、このブロックでは、次の各ビットが1番目と2番目のビット（1から番号付けされた）の合計（モジュロ2）として取得されることは容易に推測できます。

x ₅ = x ₁ + x ₂ = 1 + 1 = 0

x ₆ = x ₂ + x ₃ = 1 + 0 = 1

x ₇ = x ₃ + x ₄ = 1 + 0 = 1

など

式を使用して期待値を計算します

各ブロックについて、T _iの値を計算します。

次に、セットTに基づいて、次のようにセットv ₀ 、...、v ₆を計算します。

T _i <= -2.5の場合、v ₀ ++
-2.5 <T _i <= -1.5の場合、v ₁ ++
-1.5 <T _i <= -0.5の場合、v ₂ ++
-0.5 <T _i <= 0.5の場合、v ₃ ++
0.5 <T _i <= 1.5の場合、v ₄ ++
1.5 <T _i <= 2.5の場合、v ₅ ++
T _i > 2.5の場合、v ₆ ++

7つの可能な結果があります。つまり、自由度7-1 = 6のカイ2乗を計算します。

テストの確率πiはハードコードされており、それぞれ0.010417、0.03125、0.125、0.5、0.25、0.0625、0.020833です。（より多くの自由度のπiは、[2]で与えられる式によって計算できます）。

P値を計算する：

結果が0.01より大きい場合、シーケンスはランダムと見なされます。実際のテストでは、n> = 10 ^ 6およびMを500から5000の範囲にすることをお勧めします。

サブシーケンステスト

元のシーケンス内の長さ「m」ビットのすべての種類のシーケンスを見つける頻度が分析されます。さらに、各サンプルは個別に検索されます。見つかったサンプルを別のサンプルに「重ねる」ことができます。明らかに、すべての種類のサンプルの数は2 ^mです。シーケンスが十分に大きくランダムである場合、これらのサンプルのそれぞれを見つける確率は同じです。（ちなみに、m = 1の場合、このテストは既に説明した比率「0」または「1」のテストに「縮退」します）。

テストは[8]および[11]に基づいています。サンプルの発生頻度が真にランダムなシーケンスの同じ頻度にどの程度対応するかを特徴付ける2つのインジケーター（∇ψ2 _mおよび∇2ψ2 _m ）が記述されています。例でアルゴリズムを示します。

長さn = 10のシーケンス0011011101と、m = 3を指定します。

最初に、3つの新しいシーケンスが形成されます。各シーケンスは、シーケンスのm-1個の最初のビットをその末尾に追加することによって取得されます。判明した：

m = 3の場合：0011011101 00（末尾に2ビットを追加）
m-1 = 2の場合：0011011101 0（末尾に1ビットを追加）
m-2 = 1：0011011101の場合（ソースシーケンス）

次に、長さm、m-1、m-2のすべてのブロックの出現頻度をそれぞれ見つけます。

v ₀₀₀ = 0、v ₀₀₁ = 1、v ₀₁₀ = 1、v ₀₁₁ = 2、v ₁₀₀ = 1、v ₁₀₁ = 2、v ₁₁₀ = 2、v ₁₁₁ = 0
v ₀₀ = 1、v ₀₁ = 3、v ₁₀ = 3、v ₁₁ = 3
v ₀ = 4、v ₁ = 6

式を使用して必要な統計を計算します。

代替：

次に：

合計値：

したがって、両方のP値は0.01より大きいため、シーケンスはランダムとして認識されます。

近似エントロピー

近似エントロピー法は、最初は医学、特に心臓病で最初に証明されました。一般に、古典的な定義によれば、エントロピーはカオスの尺度です。それが高いほど、予測不可能な現象が増えます。良くも悪くも、それは文脈に依存します。暗号化で使用されるランダムシーケンスの場合、高いエントロピーを持つことが重要です。これは、すでにあるものに基づいて後続のランダムビットを予測することが困難であることを意味します。しかし、たとえば、ランダムな値について、特定の期間で測定された心拍数をとる場合、状況は異なります：心拍数の変動性が低いほど、心臓発作やその他の不快な現象が少ないことを証明する多くの研究（たとえば[12]）があります。明らかに、人間の心臓は一定の頻度で鼓動することはできません。ただし、心臓発作で死亡する人もいれば、そうでない人もいます。したがって、近似エントロピーの方法により、現象の出現が実際にランダムであるかどうかを推定できます。

具体的には、このテストでは、特定の長さ（m）のすべての種類のサンプルの出現頻度を計算し、次に同様の頻度を計算しますが、すでに長さm + 1のサンプルについて計算します。次に、頻度分布がカイ二乗基準分布と比較されます。前のテストと同様に、サンプルが重複する場合があります。

例を示します。シーケンス0100110101（長さn = 10）が与えられ、m = 3を取るとします。

まず、最初のm-1ビットでシーケンスを補完します。 0100110101 01になります。

8つのさまざまなブロックのそれぞれの発生を計算します。それは判明します：

k ₀₀₀ = 0、k ₀₀₁ = 1、k ₀₁₀ = 3、k ₀₁₁ = 1、k ₁₀₀ = 1、k ₁₀₁ = 3、k ₁₁₀ = 1、k ₁₁₁ = 0

式C _i ^m = k _i / nに従って対応する周波数を計算します。

C ₀₀₀ ³ = 0、C ₀₀₁ ³ = 0.1、C ₀₁₀ ³ = 0.3、C ₀₁₁ ³ = 0.1、C ₁₀₀ ³ = 0.1、C ₁₀₁ ³ = 0.3、C ₁₁₀ ³ = 0.1、C ₁₁₁ ³ = 0

同様に、長さm + 1 = 4のサブユニットの出現頻度を考慮します。すでに2 ⁴ = 16があります：

0011 ⁴ =0100 ⁴ =0110 ⁴ =1001 ⁴ =1101 ⁴ = 0.1、0101 ⁴ = 0.2、1010 ⁴ = 0.3 その他の周波数= 0。

φ3とφ4を計算します（自然対数であることに注意してください）：

カイ2乗を計算します。

P値：

結果の値は0.01より大きいため、シーケンスはランダムとして認識されます。

累積量テスト

元のシーケンスの各ゼロビットを-1、各シングルビットを+1として、合計を計算します。直観的には、シーケンスがランダムであればあるほど、この量はゼロになる傾向が速くなります。一方、100個のゼロと100個のユニットが連続して与えられているとします：00000 ... 001111 ... 11。ここで合計は0になりますが、 このようなシーケンスをランダムに「手は上がりません」と呼ぶことは明らかです。したがって、より深い基準が必要です。そして、この基準は部分的な量です。最初の要素から量を徐々に検討します。

S ₁ = x ₁

S ₂ = x ₁ + x ₂ S ₃ = x ₁ + x ₂ + x ₃ ...

S _n = x ₁ + x ₂ + x ₃ + ... + x _n

次は、これらの合計の数z =最大です。

最後に、P値は次の式に従って考慮されます（その導出については、[9]を参照）。

どこで：

ここで、Φは標準正規確率変数の分布関数です。標準正規分布はよく知られたガウス分布（鐘の形）であり、数学的な期待値は0、分散は1であることを思い出してください。次のようになります。

結果のP値が0.01より大きい場合、シーケンスはランダムと見なされます。

ちなみに、このテストには2つのモードがあります。最初に調べたモードと、2番目に、最後の要素から量が計算されます。

ランダム偏差テスト

このテストは前のテストに似ています：同様の方法で、正規化されたシーケンスの部分的な合計（つまり、-1と1で構成される）が考慮されます。シーケンス0110110101が与えられ、S（i）が1からi番目の要素までの部分和であるとします。シーケンスS（i）の最初と最後に「0」を追加した後、これらのポイントをグラフに描画します。これは、さらなる計算の整合性のために必要です。

グラフが水平軸と交差する点に注意してください-これらの点は、シーケンスをいわゆるものに分割します。 サイクル 。ここには、{0、-1、0}、{0、1、0}および{0、1、2、1、2、1、2、0}の3つのサイクルがあります。さらに、これらのサイクルのそれぞれは、異なる状態を連続的にとると言われています。たとえば、最初のサイクルは、状態「0」を2回、状態「-1」を1回とします。このテストでは、-4から4の状態が重要です。これらの状態のすべての発生を次の表にリストします。

状態（x）	サイクル番号1	サイクル番号2	サイクル番号3
-4	0	0	0
-3	0	0	0
-2	0	0	0
-1	1	0	0
1	0	1	3
2	0	0	3
3	0	0	0
4	0	0	0

この表に基づいて、別の表を作成します。特定の状態をとるサイクルの数は水平に移動します。

状態（x）	一度も	1回	3回
-4	3	0	0
-3	3	0	0
-2	3	0	0
-1	2	1	0
1	1	1	1
2	2	0	1
3	3	0	0
4	3	0	0

次に、8つの状態のそれぞれについて、統計のカイ2乗が次の式で計算されます。

ここで、v _k （x）は特定の状態のテーブル内の値、Jはサイクル数（3があります）、πk（x）は状態「x」が真にランダムな分布でk回発生する確率です（既知）。

たとえば、x = 1の場合、次のようになります。

残りのxの πの値については、 [2]を参照してください。

P値を計算します：

0.01より大きい場合、ランダム性について結論が出されます。その結果、8つのP値を計算する必要があります。 0.01を超えるものもあれば、少ないものもあります。この場合、シーケンスの最終決定は他のテストに基づいて行われます。

任意の偏差のテストのバリエーション

前のテストとほとんど同じですが、より広い条件セットが使用されます：-9、-8、-7、-6、-5、-4、-3、-2、-1、+ 1、+ 2、+ 3、+ 4、+ 5、+ 6、+ 7、+ 8、+ 9。ただし、主な違いは、ここではP値がガンマ関数（igamc）とカイ2乗ではなく、誤差関数（erfc）によって計算されることです。正確な式については、読者はソース文書を参照できます。

以下は、トピックを掘り下げたいかどうかを確認できるソースのリストです。

csrc.nist.gov/groups/ST/toolkit/rng/stats_tests.html
csrc.nist.gov/groups/ST/toolkit/rng/documents/SP800-22rev1a.pdf
中央極限定理
Anant P. Godbole and Stavros G. Papastavridis、（ed）、Runs and patterns in probability：選択された論文。ドルドレヒト：Kluwer Academic、1994
Pal Revesz、ランダムおよび非ランダム環境でのランダムウォーク。シンガポール：1990年ワールドサイエンティフィック
I. N.コバレンコ、確率論とその応用、1972
O. Chrysaphinou、S。Papastavridis、「一連の独立した試験におけるパターンの重複出現数の限界定理」。確率理論および関連分野、Vol。 79、1988
IJグッド、「サンプリング数の連続テストおよびランダム性のその他のテスト」ケンブリッジ、1953
A. Rukhin、「ランダム性をテストするための近似エントロピー」、Journal of Applied Probability、2000
Burlekampアルゴリズム-マッセイ
DE Knuth、コンピュータープログラミングの芸術。巻 1998年2および3
www.ncbi.nlm.nih.gov/pubmed/8466069

状態（x）	一度も	1回	3回
-4	3	0	0
-3	3	0	0
-2	3	0	0
-1	2	1	0
1	1	1	1
2	2	0	1
3	3	0	0
4	3	0	0

状態（x）	一度も	1回	3回
-4	3	0	0
-3	3	0	0
-2	3	0	0
-1	2	1	0
1	1	1	1
2	2	0	1
3	3	0	0
4	3	0	0

NISTメソッドによるバイナリシーケンスのランダム性の統計的検証

ランダムバイナリシーケンス

ゼロおよび対立仮説

周波数ビットテスト

周波数ブロックテスト

同一の連続ビットのテスト

ブロック内のユニットの最長シーケンスをテストします

バイナリマトリックスランクテスト

スペクトルテスト

重複しないパターンのテスト

交差する交差パターンのテスト

ユニバーサルマウアーテスト

線形難易度テスト

サブシーケンステスト

近似エントロピー

累積量テスト

ランダム偏差テスト

任意の偏差のテストのバリエーション

More articles:

状態（x）	一度も	1回	3回
-4	3	0	0
-3	3	0	0
-2	3	0	0
-1	2	1	0
1	1	1	1
2	2	0	1
3	3	0	0
4	3	0	0