Information Technology Reference
In-Depth Information
Table 5.
Sensitivity of randomness tests toward some transformations
Tests
σ
c
σ
l
−
rot
σ
f
i
σ
rvs
σ
d
Frequency
0
0
1
0
2
Overlapping template
2
1
1
0
2
Longest run of ones
2
1
1
0
2
Runs
0
1
1
0
2
Random walk height
0
1
1
2
2
Random walk excursion
0
1
1
2
2
Linear complexity
1
2
2
2
2
1-error linear complexity
1
2
0
2
2
Maximum order complexity
0
1
2
2
2
Lempel-Ziv
0
1
1
2
2
In Table 5, sensitivity of the tests selected in previous section are given accord-
ing to
σ
c
,σ
l−rot
,σ
f
i
,σ
rvs
and
σ
d
l
. As observed from the Table 5, some of the
transformations do not have any effect on the test results. Complementing the
input sequences only affect the results of overlapping template and longest run of
ones tests. However, for the overlapping template test, instead of complement-
ing the whole sequence, it is also possible to complement the input template
which would result in the same
p
-value.
l
-rotation affects the results of linear
complexity and 1-error linear complexity tests, whereas flipping
i
th
bit affects
the results of linear complexity and maximum order complexity tests. Reversing
the sequences significantly changes the outputs of tests based on random walks
and complexity measures. However, for balanced sequences reversing the output
of random excursion test does not affect the output. Taking the
l
th
derivative of
sequences significantly affect all test results available in our set. So, taking the
l
th
derivative seems to be a good choice of transformation to design new tests.
It is obvious that the independence of
T
(
σ
(
S
)) and
T
(
S
) is not enough to
justify adding
T
(
σ
(
·
)) to the suite. It should also be independent of other tests
in the suite. As an example, applying the frequency tests to the first derivative
of the sequence is equivalent to applying the runs test.
5Con lu on
Statistical testing plays an important role in analyzing the strength of random
number generators and there are various test suites in the literature for this pur-
pose. Generators which pass suites with high coverage engender more confidence.
In this study, we emphasize the importance of independence of randomness tests
in test suites and present some theoretical and experimental results. We ex-
perimentally observe that frequency, overlapping template (with input template
111), longest run of ones, random walk height tests and maximum order complex-
ity tests produce correlated results for short sequences. These correlations should
be considered while analyzing generators using short sequences. The strength of
these correlations is likely to decrease as the input lengths increase, but in the
