Information Technology Reference
In-Depth Information
One Level: (
s
1
,...,s
n
)
→
Evaluate
T
T
Two Level: (
s
1
,...,s
m
)
,...
(
s
n
−
m
+1
,...,s
n
)
→
Evaluate
T
1
,...,T
N
T
1
T
N
Fig. 1.
Multi Level Testing
statistics,
t
1
,t
2
,...,t
N
. Then, using standard goodness of fit tests, the empirical
distribution of
t
i
values is compared to the the theoretical distribution of the
test statistic under
H
0
. This is called level-2 testing (See Fig. 1). To increase
the power, the level of tests may be increased further. The level-2 version of
frequency test is the
frequency test within a block
[1] that focuses on the weight
of disjoint parts of a given sequences.
3
Independence of Tests
There are extensive number of randomness tests in the literature and to design a
test suite a careful selection should be done. Many generators may appear to be
random according to a number of tests, but may be non-random when subjected
to another test, therefore the variety or the coverage of the tests used in the test
suite should be high enough. However, including dependent tests may result in
wrong conclusions about the generators.
Two tests
T
1
and
T
2
are considered to be independent if the distribution
of their test statistics
t
1
and
t
2
(and corresponding
p
-values) are independent,
that is
Pr
(
t
1
|
t
2
)=
Pr
(
t
1
)
,
(2)
and visa versa.
In this section, we analyze the relation between some of the commonly used
tests and try to observe if there exists any statistically significant correlation. We
consider ten level-1 tests, which are also suitable for testing to short sequences.
Given a sequence (
s
1
,s
2
,...,s
n
)oflength
n
, each test defines a test statistic as
described below.
-
Frequency Test :
The test statistic is the weight of the sequence, that is
t
=
s
1
+
...
+
s
n
, taking values between 0 and
n
.
-
Overlapping Template Test:
Test statistic is the number of occurrences of a
m
bit pattern
a
throughout the sequence, that is
t
=
|{
i
|
(
s
i
,...,s
i
+
m−
1
)=
a
,
1
≤
i
≤
n
−
m
+1
}|
.
(3)
For our experiments,
a
is chosen to be 111.
-
Longest Run of Ones Test:
Test statistic is the length of the longest run of
ones, that is
t
=max
{
m
|
s
i
=
s
i
+1
...
=
s
i
+
m
=1
,
1
≤
i
≤
n
}
,
(4)
taking values between 0 and
n
.
