Birthday Spacing Test
Test Purpose
The test uses simulation to evaluate the randomness of groups of 24 sequential bits of the integer output of a BRNG. The test analyzes all possible groups of the kind, that is, for example, from 0 to 23 bit, from 1 to 24 bit, and so on.
First Level Test
The first level test selects at random
m
= 210 ”birthdays” from a ”year” of
n
= 224 days. Then the test computes the spacing between the birthdays for each pair of sequential birthdays. The test then uses the spacings to determine the
K
value, that is, the number of pairs of sequential birthdays with the spacing of more than one day. In this case
K
should have the distribution close to the Poisson distribution with the
l
= 16 parameter. The first level test determines 200 values of
K
(j
j
= 1, 2, ..., 200). To obtain the p-value
p
, the test applies the chi-square goodness-of-fit test to the determined values.
The integer output lists different interpretations for each BRNG. In the table below, NB stands for the number of bits required to represent a random number in integer arithmetic, WS stands for the machine word size, in bits, used in integer random number generation.
BRNG
| Integer Output Interpretation
|
---|---|
MCG31m1
| Array of 32-bit integers. Each 32-bit integer uses the following bits:
0-30. NB=31, WS=32.
|
R250
| Array of 32-bit integers. Each 32-bit integer uses the following bits:
0-31. NB=32, WS=32.
|
MRG32k3a
| Array of 32-bit integers. Each 32-bit integer uses the following bits:
0-31. NB=32, WS=32.
|
MCG59
| Array of 64-bit integers. Each 64-bit integer uses the following bits:
0-58. NB=59, WS=64.
|
WH
| Array of quadruples of 32-bit integers. Each 32-bit integer uses the following bits:
0-23. NB=24, WS=32.
|
MT19937
| Array of 32-bit integers. Each 32-bit integer uses the following bits:
0-31. NB=32, WS=32.
|
MT2203
| Array of 32-bit integers. Each 32-bit integer uses the following bits:
0-31. NB=32, WS=32.
|
SFMT19937
| Array of quadruples of 32-bit integers. Each 32-bit integer uses the following bits:
0-32. NB=32, WS=32.
|
PHILOX4X32X10
| Array of 32-bit integers. Each 32-bit integer uses the following bits:
0-31. NB=32, WS=32.
|
ARS5
| Array of 32-bit integers. Each 32-bit integer uses the following bits:
0-31. NB=32, WS=32.
|
The test generates the dates of the birthdays in the following way:
- Selects thebs,bs +1, ...,bs +23bits from the next WS-bit integer of the integer output ofviRngUniformBits.
- Treats the selected bits as a 24-bit integer, that is, the number of the date on which the next birthday takes place and thus generates a birthday.
- The test performs the steps 1 and 2mtimes to generatembirthdays taken that the year consists ofndays. The legitimate valuessare different for each base generator (see the table above): 0 £s£ NB - 24.
Second Level Test
The second level test performs the first level test ten times for the fixed
s
. The test applies the Kolmogorov-Smirnov goodness-of-fit test with Anderson-Darling statistics to the obtained set of
p
j
(j
= 1, 2 , ..., 10). If the resulting p-value is
p
< 0.05 or
p
> 0.95, the test fails for the given
s
.
Final Result Interpretation
The second level test performs ten times for each 0 £
s
£ NB - 24. The test computes the FAILs percentage for the failed second level tests. The final result is the minimal percentage of the failed tests FAIL = min(FAIL0
, FAIL1
, ..., FAILNB-24
) for 0 £
s
£ NB - 24. The applicable result is the value of FAIL < 50%. Thus, the test determines if it is possible to select 24 random bits from every element of the integer output of the generator.
- The integer output for the WH generator is the quadruples of the 32-bits values (x,iy,iz,iw). In each 32-bit value only the lower 24 bits are significant.i
- The second level test performs ten times for thexelement. Then the test computes the FAILipercentage the failed second level tests.x
- The second level test performs ten times for they. Then the test computes the FAILipercentage for the failed second level tests.y
- The test performs the same procedure to compute the FAILand FAILzvalues.w
The final result is the minimal percentage of the failed tests FAIL = min(FAIL, FAIL, FAIL, FAIL). The acceptable result is the value of FAIL < 50%.
x
y
z
w
The test determines if it is possible to select 24 random bits from the fixed element
x, y, z
or
w
for each element of the integer output of the generator.
Tested Generators
Function Name
| Application
|
---|---|
| not applicable
|
| not applicable
|
| not applicable
|
| applicable
|