CRYPTREC Report 2005
(CRYPTREC-RP-2000-2005)
付録 ６

擬似乱数検定のための
CRYPTREC ミニマムセット仕様書

平成 18 年 2 月

CRYPTREC 事務局

283

背景

1

電子政府推奨暗号リストにおける擬似乱数系では、SHA-1 を使った擬似乱数生成器が例示されている。しかし、用途によっては、例示された擬似乱数生成器以外でも、暗号学的に安全性が確認できれば、用途によっては利用できる場合もある。そこで電子政府で使用される擬似乱数生成器
が、少なくとも高い乱数性を持つことを検証するためのツールが必要と考えられている。
また、乱数の検定法には様々な観点からの検定法が存在しており，それらを複数集めて検定ツール
としてまとめられたものもいくつか存在する。代表的なものとしては、NIST FIPS PUB 140-2、NIST Special Publication (SP) 800-22、DIEHARD、 The Art of Computer programming 準数
値算法 D.Knuth 著に記載されたものなどが知られている。しかし、これらの検定ツールを比較検討すると、

1) 検定ツールごと採用されている検定法が異なり、検定法の選択基準が明確になっていない
2) 同じ検定手法でも検定ツール毎に閾値等の設定値が異なる場合があるなど問題点が存在する。特に、NIST FIPS PUB 140-2 と NIST SP 800-22 には、いくつかの検定
法に不具合があることを指摘した学術論文があり、さらに、2002 年度版暗号技術評価報告書においても同様の指摘がなされている。
他方、暗号モジュール委員会で検討中の暗号モジュール評価においても乱数検定が必要になるという背景があり、2003 年度に擬似乱数生成系調査ワーキンググループ設置し、CRYPTREC としての乱数検定ミニマムセットの策定を目標に、擬似乱数生成系の調査および検定法の調査を開始した。

2003 年度の調査の結果、CRYPTREC の乱数検定ミニマムセットにおいては理論的な裏付けが無
いものについては、積極的には採用しない方向に決まった。また、理論的裏付けがあったとしても、計算機実験が行なえる程度の実際的な追試を行い、閾値等の設定値が適切かどうかの確認が必要であるとの判断となった。ただし乱数検定法は全部で 250 種類ほど知られており、全部を確認す
ることは非現実的であるので、2004 年度以降は調査の範囲を絞ることも課題となった。その結果、2004 年度以降の活動方針を以下のように定めた。
1) FIPS 140-2、SP 800-22、DIEHARD で採用されている各検定法の調査範囲の絞り込みと理論的根拠の確認及び計算機実験による検証
2) 1) の結果を踏まえての CRYPTREC 擬似乱数検定ミニマムセットへの導入の判断を行う
3) CRYPTREC 擬似乱数検定ミニマムセットの暗号モジュール評価ツールへの組み込みの検討を行う

2004 年度としては、2003 年度に定めた活動方針に添って以下の活動を行なった。
1) FIPS 140-2、SP 800-22、DIEHARD で採用されている各検定法の調査範囲の絞り込みと理論的根拠の確認及び計算機実験による検証

2) 1) の結果を踏まえての CRYPTREC 擬似乱数検定ミニマムセットへの導入の判断を行う
特に，1) の検定方法に関しては、離散フーリエ変換検定するための数学理論を構築するための予備調査と 2003 年度未解決であった分散値の理論的確認と、擬似乱数生成系に対する各種検定方式の理論的根拠の確認及び計算機実験による検証を実施した。

284

2005 年度には、2003 年度および 2004 年度の調査結果に基づき、CRYPTREC としての乱数検定のためのミニマムセットとして、NIST で公表している SP 800-22 の 16 種類の検定法の中から 14
種類を採択し、「乱数検定ミニマムセット仕様」として本仕様書の作成を行なった。

285

2

乱数検定のためのミニマムセット案
乱数検定のためのミニマムセットとして下記のものを定める

1. 頻度検定 (Frequency Test)
2. ブロック単位の頻度検定 (Frequency Test within a Block)
3. 連検定 (Runs Test)
4. ブロック単位の最長連検定 (Test for the Longest Run of Ones in Block)5. 2 値行列ランク検定 (Binary Matrix Rank Test)
6. 重なりのないテンプレート適合検定 (Non-overlapping Template Matching Test)
7. 重なりのあるテンプレート適合検定 (Overlapping Template Matching Test)
8. Maurer のユニバーサル統計検定 (Maurer’s ”Universal Statistical ” Test)
9. 線形複雑度検定 (Linear Complexity Test)
10. 系列頻度検定 (Serial Test)
11. 累積和検定 (Cumulative Sums (Cusum) Test)
12. ランダム回遊検定 (Random Excursions Test)
13. 変形ランダム回遊検定 (Random Excursions Variant Test)
14. 近似エントロピー検定 (Approximate Entropy Test)

286

3

検定に対する可否判断基準
ミニマムセットで採用されているすべての検定は、0 と 1 からなる乱数列を対象としている。また、ミニマムセットの検定では、各検定ごとに p-value が得られる。p-value とは、真の乱数生成器
が検定を行っている系列よりも乱数らしからぬ系列を生成する確率である。例として、頻度検定の場合を考える。このとき、p-value は以下のように求める。試行としては 100 万系列を 1000 本考える。

1. X1 , X2 , · · · , Xn を {1, −1} の中の値をとる n 個の確率変数とし、Sn = X1 + X2 + · · · + Xnとする。

2. 系列が真の乱数生成器からの出力ならば、
µ = 0
σ2

= n

lim P

!

"

Φ(z) =# zとなるので、中心極限定理より、n→∞となる。なお、Sn√ ≤zn= Φ(z)

2
1√ e−x /2 dx
2π−∞は標準正規分布の累積分布関数である。

√
3. 統計量 s = |Sn |/ n を考える。このとき、
P (s ≤ z) = 2Φ(z) − 1が得られ、

p-value = 2[1 − Φ(s)]である。なお、ミニマムセットでは、Φ(z) の代わりに誤差関数# ∞22√ e−x dx
erf c(z) =
π
z
を用いれば

√
p-value = erf c(s/ 2)となる。
ミニマムセットでは、p-value< 0.01 のときに良い乱数生成器ではないと判断する。
なお、統計量がカイ 2 乗統計量の場合、p-value は、

# ∞
z

1
2Γ( N2 )! " N2 −1tte− 2 dt2により求める。ただし、N は χ2 分布の自由度であり、# ∞Γ(α) =
xα−1 e−x dx
0

287

である。
ミニマムセットでは、1 本の標本系列に対する仮説検定で乱数生成アルゴリズムを評価するのは無意味であるという考え方から、複数の標本系列 (NIST では 1000 程度を推奨している) に対し検定を行い、

1. p-value の一様性
2. p-value が 0.01 より大きくなる割合
から乱数列の評価を行う。1. では、得られた p-value が区間 [0, 1) で一様に分布しているかどうかを調べるために、[0, 1) を 10 の区間に分割し、分割した区間ごとの頻度が一様になっているかどうかをカイ 2 乗検定にて検定する。カイ 2 乗検定により得られた p-value が 0.0001 以上ならば、乱数列は良い乱数生成器であると判断する。また、2. では、標本の数を m としたとき、0.01 以上となる p-value の数の割合が$0.99 ± 30.99 × 0.01mの範囲に入っている場合は、乱数列は良い乱数生成器であると判断する。

288

4

検査の概要と可否判断

4.1

頻度検定

乱数列のビットの出現頻度を求めその度数分布が一様になっているかどうかを標準正規分布の誤差関数にて検定する。

入力

{εi }

n

:

0 か 1 の値をとる乱数列:乱数列の長さ（乱数の個数）100 万系列を 1000 本 100 万系列を 1000
本

出力

erf c(sobs ):標準正規分布の誤差関数からの p-value

処理内容

ステップ 1:

系列を ± に変換し、Sn = X1 + X2 + · · · + Xn (Xi = 2εi − 1) を計算

ステップ 2:ステップ 3:する。

Sn
統計値 sobs = | √| を計算する。
n√p-value = erf c(sobs / 2) を計算する。

289

4.2

ブロック単位の頻度検定

乱数列の文字の出現頻度を求めその度数分布が一様になっているかどうかをカイ 2 乗検定にて検
定する。

入力

各ブロックのビット長

M
{εi }
n

:
:
:

乱数列の長さ（乱数の個数）100 万系列を 1000 本

出力χ20 (obs):

カイ 2 乗統計量からの p-value

処理内容

ステップ 1:n
入力系列を N = % M& の重なりの無いブロックに分割する。使わないステップ 2:ステップ 3:ステップ 4:0 か 1 の値をとる乱数列

ビットは無視する。
%Mε(i−1)M +j

を 1 ≤ i ≤ N に対して計算する。
%
カイ 2 乗統計量 χ を χ2 (obs) = 4M i=1 N (πi − 1/2)2 により計算す

πi =

j=1

M

2

る。

p-value = igamc(N/2, χ2 (obs)/2) を計算する。ここで igamc は不完全なガンマ関数である。

290

4.3

連検定

区間 [0, 1) 上を分布する乱数列を上昇連、下降連で分割し、部分列の長さでクラスを定義する。
部分列を長さに応じてクラスに割り当て、その度数をカイ 2 乗検定にて検定し、連の偏りを調べる。なお、乱数列が 0 と 1 からなる乱数の場合は、区間 [0, 1) 上に分布する乱数列への変換が必要
である。

入力

出力
処理内容

n

:

ビット列の長さ{εi }:0 と 1 の c 中から値をとる乱数列

p-value:

カイ 2 乗統計量からの p-value（

ステップ 1:ステップ 2:

事前に 1 が出力される確率 π =

%

i

n

εi

を計算する

頻度テストをパスするかどうか決定する。もしも τ ≤ |π − 1/2| が示されるならば連検定を行う必要は無い。検定を行う必要が無い場合は

p-value は 0.0000 に設定される。ここで τ = √2n は事前に定義されてステップ 3:いなければならない。
%n−1
検定値 Vn (obs) = k=1 r(k) + 1 を計算する。ここで、εk = εk+1 ならば r(k) = 0 で、さもなければ r(k) = 1 である。
ステップ 4:√p-value = erf c( |Vn (obs)−2nπ(1−[pi)|) を計算する
2 2nπ(1−π)

291

4.4

ブロック単位の最長連検定

0 と 1 からなる乱数列を M ビット単位で分割し、最長連の長さに応じて各部分列を 7 個のクラ
スに割り当てその度数をカイ 2 乗検定にて検定し最長連の長さの偏りを調べる。なお、M は乱数列の長さによって決まる。

入力

0 と 1 の中から値をとる乱数列

{εi }
n

:
:

乱数列の長さ（乱数の個数）100 万系列を 1000 本

M:各ブロックのビット数

出力p-value:

カイ 2 乗統計量からの p-value

処理内容

ステップ 1:

乱数列を長さ M のブロックに分割する。ただし、ブロックサイズは、

ステップ 2:128 ≤ n < 6272 のときは M = 8、6272 ≤ n < 750, 000 のときは
M = 128、750, 000 ≤ n のときは M = 10000 とする。

M = 8 のときは、各ブロックを 1 の最長連の長さに応じて、f0 から f3の K = 4 個のクラスに分割し、各クラスの度数を求める。クラスに対応する長さおよびクラスの確率は
クラス

f0

f1

f2

f3

度数

〜1

2

3

4〜

確率

0.21480.36720.23050.1875となる。また、M = 128 のときは、以下のような K = 6 個のクラスに割り当てる。
クラス

f0

f1

f2

f3

f4

f5

度数

〜4

5

6

7

8

9〜

確率

0.11740.24300.24930.17520.10270.1124となる。また、M = 10000 のときは、以下のような K = 7 個のクラ
スに割り当てる。
クラス

ステップ 3:ステップ 4

:

f0

f1

f2

f3

f4

f5

12

13

14

15

度数

〜10

11

確率

0.08820.20920.2483 0.1933 0.1208 0.0675
K& (fi − N πi )2
カイ 2 乗統計量 χ2 (obs) =
を求める。
N πi
i=0

f6
16〜
0.0727χ2 (obs) は、自由度 K − 1 の χ2 分布に従うので、この分布から p-valueを計算する。

最長連検定は、長さ 20000 ビットの 1 ブロックに対する検定である。

292

4.5

2 値行列ランク検定：(32×32) の 2 値行列ランク検定

0 と 1 からなる乱数列の 1024 ビットの部分列から (32×32) の 2 値行列を構成し、各部分列を行列のランクに応じてを 3 個のクラスに割り当て、その度数をカイ 2 乗検定にて検定しランクの偏り
を調べる。

入力

{Xi }

:

0 と 1 の中から値をとる乱数列

出力p-value:

カイ 2 乗統計量からの p-value

ステップ 1ステップ 2::ステップ 3:行列のランクを、29 以下、30, 31, 32 の 4 個のクラスに分ける。
Xi を列の先頭から順に 32 ビットずつ取り出し、32 ビットの整数からなる新しい列 {Yi } を作る。

処理内容連続する 32 個の Yi を順に並べて GF (2) 上の 32 × 32 行列を作る。32個の組は (Y1 , Y2 , · · · , Y32 ), (Y33 , Y33 , · · · , Y64 ) のように重ね合わせずに作っていく。
ステップ 4:ステップ 3 で得られた行列のランクを計算し、ランクに応じてクラス

ステップ 5::ステップ 2〜4 を 40,000 回くり返す。

ステップ 6の度数に加えていく。各クラスの度数を f0 , f1 , f2 , f3 とする。

カイ 2 乗統計量 χ20 を計算する。各クラスの確率の値は、次の表の値を用いる。χ20 は自由度 3 の χ2 分布に従うので、この分布から p-value を

計算する。
〜28

29

30

31

0.0052854502

0.1283502644

0.5775761902

0.2887880952

293

4.6

重なりの無いテンプレート適合検定

0 と 1 からなる乱数列を 8 つのブロックに分割し、各ブロックごとに m ビットの窓を先頭からスライドさせ、窓と m 文字のテンプレートが適合する回数を調べる。8 ブロックそれぞれの適合回数をカイ 2 乗検定にて検定し適合回数の偏りを調べる。

入力

0 と 1 の中から値をとる乱数列

{Xi }
n

:
:

m
B

:
:

m ビットのテンプレート

出力p-value:

カイ 2 乗統計量からの p-value

処理内容

ステップ 1::

乱数列を長さ M = 131, 072 = 217 の N = 8 個のブロックに分割する。

ステップ 2乱数列の長さ（乱数の個数）100 万系列を 1000 本
テンプレートの長さブロック j のテンプレートの適合回数を Wj とする。m ビットの窓を
ブロックの先頭にセットし、テンプレートが適合しないときは、窓をステップ 3:ステップ 4:

1 ビットずらし、適合するときは窓を m ビットずらす。
中心極限定理より、各ブロックの適合回数はは平均µ = (M −m+1)/2m 、!
"
12m − 1
分散 σ 2 = M−の正規分布に従うことを用いて、カイ
2m
22m
N
&
(Wj − µ)2
2 乗統計量 χ2 (obs) =
を求める。
σ2
j=1
χ2 (obs) は、自由度 N の χ2 分布に従うので、この分布から p-value を計算する。

ミニマムセットでは、テンプレートの長さを 2 から 10 まで選択できるが、9 または 10 が推奨されている。なお、NIST のツールでは、乱数列の長さが 1,000,000 の場合のみ検定することがで
きる。

294

4.7

重なりのあるテンプレート適合検定

0 と 1 からなる乱数列を 968 個のブロックに分割し、各ブロックを m 文字のテンプレートが適合する回数により 6 個のクラス割り当て、その度数をカイ 2 乗検定にて検定し適合回数の偏りを調べる。

入力

0 と 1 の中から値をとる乱数列

{Xi }
n

:
:

m
B

:
:

m ビットのテンプレート

出力p-value:

カイ 2 乗統計量からの p-value

処理内容

ステップ 1::

乱数列を長さ M = 1032 の N = 968 個のブロックに分割する。

ステップ 2乱数列の長さ（乱数の個数）100 万系列を 1000 本
テンプレートの長さブロック j のテンプレートの適合回数を Wj とする。m ビットの窓を
ブロックの先頭から 1 ビットずつずらして行き、テンプレートと窓の適合回数を数える。

ステップ 3:

適合回数 0 のクラスを f0 、1 のクラスを f1 、2 のクラスを f2 、3 のク

ラスを f3 、4 のクラスを f4 、5 以上のクラスを f5 とし、ブロックの適ステップ 4:

合回数 Wj から各クラスの度数を求める。
5&(fi − N πi )カイ 2 乗統計量 χ2 (obs) =を求める。クラス fi に対応
N πi
する確率 πi は、ステップ 5:i=0

π0 = e−ηη
π1 = e−η
2
ηe−η
π2 =
[η + 2]8−η ' 2
(
η
ηe
+η+1
π3 =
8 '6
(
−η
3
ηe
η
η2
3η
π4 =
+
+
+1
16 24
2
2
π5 = 1 − (π0 + π1 + π2 + π3 + π4 )となる。ただし、η = λ/2, λ = (M − m + 1)/2m である。

χ2 (obs) は、自由度 5 の χ2 分布に従うので、この分布から p-value を
計算する。

295

4.8

Maurer のユニバーサル統計検定

0 と 1 からなる乱数列における長さ L ビットのパターンの間隔を調べることにより乱数列の一様性・圧縮可能性を調べる。

入力

{Xi }
n
L

:
:
:

0 と 1 の中から値をとる乱数列乱数列の長さ（乱数の個数）100 万系列を 1000 本
ブロックの長さ

Q:

初期系列のブロック数

出力p-value:

正規分布統計量からの p-value

処理内容

ステップ 1:

乱数列を長さ L のブロックに分割し、先頭から Q ブロック分を初期セグメントとし、残りの K ブロック分をテストセグメントとする。ただステップ 2ステップ 3::

し、K = %(n − QL)/L& とする。

Tj (0 ≤ j ≤ 2L ) の初期値を Tj = 0 とし、「i 番目の L ビットブロック
を 2 進数とみなしたときの値が j のときに、Tj = i とする」という処理を初期セグメントの先頭ブロックから初期セグメントの最終ブロッ
クまで順に行う (1 ≤ i ≤ Q)。

sum の初期値を 0 とし、「i 番目の L ビットブロックを 2 進数とみなしたときの値が j のときに、sum = sum + log2 (i − Tj ) とし、さらにTj = i とする」という処理をテストセグメントの先頭ブロックからテ
ストセグメントの最終ブロックまで順に行う (Q + 1 ≤ i ≤ Q + K)。まステップ 4た、fn = sum/K を求める。

:

fn は下記の表にある平均、分散の正規分布に従うので、この分布から

p-value を計算する 。
L

平均

分散

6

5.2177052

2.954

7

6.1962507

3.125

8

7.1836656

3.238

9

8.1764248

3.311

10

9.1723243

3.356

11

10.170032

3.384

12

11.168765

3.401

13

12.168070

3.410

14

13.167693

3.416

15

14.167488

3.419

16

15.167379

3.421

296

4.9

線形複雑度検定

0 と 1 からなる乱数列を長さ M のブロックに分割し、ブロックごとの線形複雑度を求めること
により乱数列の周期性を調べる。

入力

{Xi }
n
M

:
:
:

0 と 1 の中から値をとる乱数列乱数列の長さ（乱数の個数）100 万系列を 1000 本
ブロックの長さ

出力p-value:

カイ 2 乗統計量からの p-value

処理内容

ステップ 1::

乱数列を長さ M のブロックに分割し、N = %n/m& とする。

ステップ 2ステップ 3:ステップ 4:

Berlekamp-Massey アルゴリズムを用いて、ブロック i の線形複雑度 Liを求める (i = 1, · · · , N )。
M (9 + (−1)M +1 ) (M/3 + 2/9)µ=++
を求め、Ti = (−1)M × (Li −2362Mµ) + 2/9 を求める (i = 1, · · · , N )。

Ti の値により 7 つのクラス ν0 , ν1 , · · · , ν6 を定め、各クラスの度数を求める。
クラス

Ti の範囲ν0Ti ≤ −2.5

ν1
ν2
ν3
ν4
ν5
ν6
ステップ 5:−2.5 < Ti ≤ −1.5
−1.5 < Ti ≤ −0.5
−0.5 < Ti ≤ 0.5
0.5 < Ti ≤ 1.5
1.5 < Ti ≤ 2.5
2.5 < Ti

カイ 2 乗統計量 χ20 を計算する。クラス i の確率の値 πi は、次の表の値を用いる。χ20 は自由度 6 の χ2 分布に従うので、この分布から p-valueを計算する。
クラス

確率

π00.01047π10.03125

π2

0.125

π3

0.5

π4

0.25

π5

0.0625π60.02078

297

4.10

系列頻度検定0 と 1 からなる乱数列における長さ m ビットのパターン長さ m − 1 ビットのパターン、長さm − 2 ビットのパターンが一様に出現しているかを調べることにより乱数列の一様性・圧縮可能性
を調べる。

入力

0 と 1 の中から値をとる乱数列

{Xi }
n

:
:

乱数列の長さ（乱数の個数）100 万系列を 1000 本

m:

ブロックの長さ

出力p-value:

カイ 2 乗統計量からの p-value(2 個)

処理内容

ステップ 1:

重 な り の あ るm

ビット ブ ロック の 列 を(X1 , X2 , · · · , Xm ), (X2 , X3 , · · · , Xm+1 ) · · · の よ う に 定 め る 。同 様に、重なりのある m − 1 ビットブロックの列、重なりのある m − 2

ビットブロックの列を定める。
ステップ 2ステップ 3::m ビットパターン i1 i2 · · · im の出現頻度 νi1 i2 ···im 、m−1 ビットパターン
i1 i2 · · · im−1 の出現頻度 νi1 i2 ···im−1 、m−2 ビットパターン i1 i2 · · · im−2の出現頻度 νi1 i2 ···im−2 を求める。
2m & )
n *2
2m &
Ψ2m =
ν2
−
νi1 i2 ···im − m=n i i ···i2n i i ···i i1 i2 ···im
1 2
m
1 2
m
& )
2m−1
n *2
n、Ψ2m−1=
νi1 i2 ···im−1 − m−1=
n i i ···i
2
1 2
m−1
&
2m−1
2
νi1 i2 ···im−1−n、Ψ2m−2=n i i ···i
1 2
m−1
& )
&
2m−2
n *2
2m−2
νi21 i2 ···im−2 −νi1 i2 ···im−2 − m−2 =n2ni1 i2 ···im−2

ステップ 4:i1 i2 ···im−2

n を求める。
∇Ψ2m = Ψ2m − Ψ2m−1 および ∇2 Ψ2m = Ψ2m − 2Ψ2m−1 + Ψ2m−2 を求める。
ステップ 5:∇Ψ2m は自由度 2m−1 の χ2 分布に従うので、この分布から p-value を計算する。同様に、∇2 Ψ2m は自由度 2m−2 の χ2 分布に従うので、この分布から p-value を計算する。

298

4.11

累積和検定

%i
%n
0 と 1 からなる乱数列 X1 , X2 , · · · Xn に対し、Si = j=1 (2Xj −1) および Si% = j=n−i+1 (2Xj −1) (1 ≤ i ≤ n) の絶対値の最大値を求め、その偏りを調べる。
入力:

0 と 1 の中から値をとる乱数列n:乱数列の長さ（乱数の個数）100 万系列を 1000 本

出力p-value:

正規分布統計量からの p-value(2 個)

処理内容

ステップ 1:S1 = 2X1 − 1 とし、Sk = Sk−1 + 2Xk − 1 を求める (2 ≤ k ≤ n)。さ{Xi }ステップ 2:らに、z = max1≤k≤n |Sk | を求める。[Mode 0]"!
"((n/z−1)/4 ' !
&(4k + 1)z
(4k − 1)z√√Φp − value = 1 −−Φ+nnk=(−n/z+1)/4(n/z−1)/4&k=(−n/z−3)/4

ステップ 3

:

' !
"
!
"(
(4k + 3)z
(4k + 1)z√√Φ−Φを求める。ただし、nn

Φ は標準正規分布の累積分布関数である。
S1 = 2Xn − 1、Sk = Sk−1 + 2Xn−k − 1 とし、ステップ 1、2 を行う。
[Mode 1]

299

4.12

ランダム回遊検定%i
0 と 1 からなる乱数列 X1 , X2 , · · · Xn に対し、Si = j=1 (2Xj − 1) (1 ≤ i ≤ n) を求め、Si = 0
から次に 0 になるまでを 1 つのサイクルとみなし、-4〜-1、および、1〜4 の 8 種類の状態ごとにサイクルの出現度数の偏りを調べる。

入力

0 と 1 の中から値をとる乱数列

{Xi }
n

:
:

乱数列の長さ（乱数の個数）100 万系列を 1000 本

出力p-value:

カイ 2 乗統計量からの p-value(8 個)

処理内容

ステップ 1:ステップ 2:S1 = 2X1 − 1 とし、Sk = Sk−1 + 2Xk − 1 を求める (2 ≤ k ≤ n)。さらに、0, S1 , S2 , · · · , Sn , 0 という新しい数列 S % を定める。

0 から始まり次に現れる 0 までを 1 サイクルとし、 数列 S % からサイクルを求める。なお、数列 S % のサイクル数 J が J < 500 ならば、検定を中止する。

ステップ 3:8 種類の状態値を-4〜-1、および、1〜4 とし、各サイクルごとに状態値の出現度数を求める。

ステップ 4:

状態値 x の出現度数が k となるサイクルの数を νk (x) とし、8 種類のすべての状態に対し νk (x) を求める (1 ≤ k ≤ 5)。ただし、ν5 (x) は状

態値 x の出現度数が 5 回以上のサイクル数とする。
ステップ 5:8 種 類 の す べ て の 状 態 値 に 対 し 、カ イ 2 乗 統 計 量 χ2 (obs)5&(νk (x) − Jπk (x))2を求める。ただし、
Jπk (x)=

k=0

π0 (x)

π1 (x)π2 (x)π3 (x)

π4 (x)

π5 (x)|x| = 10.50000.25000.12500.06250.03120.0312|x| = 20.75000.06250.04690.03520.02640.0791|x| = 30.83330.02780.02310.01930.01610.0804|x| = 40.08750.01560.01370.01200.01050.-733である。
ステップ 6:χ2 (obs) は自由度 5 の χ2 分布に従うので、この分布から 8 種類のすべての状態値に対する p-value を計算する。

300

4.13

変形ランダム回遊検定%i
0 と 1 からなる乱数列 X1 , X2 , · · · Xn に対し、Si = j=1 (2Xj − 1) (1 ≤ i ≤ n) を求め、-9〜-1、
および、1〜9 の 18 種類の状態の出現度数の偏りを調べる。
入力

{Xi }
n

:
:

0 と 1 の中から値をとる乱数列乱数列の長さ（乱数の個数）100 万系列を 1000 本

出力p-value:

正規分布統計量からの p-value(18 個)

処理内容

ステップ 1:ステップ 2:S1 = 2X1 − 1 とし、Sk = Sk−1 + 2Xk − 1 を求める (2 ≤ k ≤ n)。さらに、0, S1 , S2 , · · · , Sn , 0 という新しい数列 S % を定める。

0 から始まり次に現れる 0 までを 1 サイクルとし、 数列 S % からサイクルを求める。なお、数列 S % のサイクル数を J とする。

ステップ 3:18 種類の状態値を-9〜-1、および、1〜9 とし、状態値 x の出現度数 ξ(x)を求める。

ステップ 4:18 種+類 の す べ て の 状- 態 値 に 対 す る p-value を p − value =|ξ(x) − J|erf c ,
により求める。ただし、erf c は標準正規分布
2J(4|x| − 2)の誤差関数である。

301

4.14

近似エントロピー検定

0 と 1 からなる乱数列における長さ m ビットのパターン長さ m ＋ 1 ビットのパターンが一様に出現しているかを調べることにより乱数列の一様性・圧縮可能性を調べる。ただし、m < log(n) − 7
とする。

入力

0 と 1 の中から値をとる乱数列

{Xi }
n

:
:

乱数列の長さ（乱数の個数）100 万系列を 1000 本

m:

ブロックの長さ

出力p-value:

カイ 2 乗統計量からの p-value

処理内容

ステップ 1:

重 な り の あ るm

ビット ブ ロック の 列 を(X1 , X2 , · · · , Xm ), (X2 , X3 , · · · , Xm+1 ) · · · の よ う に 定 め る 。同 様に、重なりのある m + 1 ビットブロックの列を定める。
ステップ 2:

すべての m ビットパターンに対して、出現頻度 #i および Cim = #i/nを求める。ただし、i は m ビットブロックを 2 進数とみなしたときの値と
m
2&
−1
(m)
する。さらに、φ=πi log πi を求める。ただし、πi = Cjm , j =ステップ 3log2 i とする。

:

i=0すべての m + 1 ビットパターンに対して、出現頻度 #i および Cim+1 =#i/n を求める。ただし、i は m + 1 ビットブロックの値を 2 進数とみ
2m+1
&−1
(m+1)
πi log πi を求める。
なしたときの値とする。さらに、φ=

ただし、πi = Cjm+1 , j = log2 i とする。

ステップ 4:ステップ 5:i=0

カイ 2 乗統計量 χ20 = 2n[log 2 − (φ(m) − φ(m+1) )] を求める。

χ20 は自由度 2m の χ2 分布に従うので、この分布から p-value を計算す
る。

302

5

可否判定条件
以下に p-value の判定条件を定める。条件を満たさない場合はランダムでないと判定する。
表 1: 可否判定条件
検定法

判定条件

頻度検定

p-value ≥ 0.01 ならばランダムと判定

ブロック単位の頻度検定
連検定
ブロック単位の最長連検定

2 値行列ランク検定
重なりのないテンプレート適合検定
重なりのあるテンプレート適合検定

Maurer のユニバーサル統計検定
線形複雑度検定
系列頻度検定累積和検定
ランダム回遊検定
変形ランダム回遊検定
近似エントロピー検定

p-value ≥ 0.01 ならばランダムと判定
p-value ≥ 0.01 ならばランダムと判定
p-value ≥ 0.01 ならばランダムと判定
p-value ≥ 0.01 ならばランダムと判定
p-value ≥ 0.01 ならばランダムと判定
p-value ≥ 0.01 ならばランダムと判定
p-value ≥ 0.01 ならばランダムと判定
p-value ≥ 0.01 ならばランダムと判定
p-value ≥ 0.01 ならばランダムと判定
p-value ≥ 0.01 ならばランダムと判定
p-value ≥ 0.01 ならばランダムと判定
p-value ≥ 0.01 ならばランダムと判定
パラメータの範囲を狭め、log(n) − 7 以下ならばランダムと判定

303