Stringency of Tests for Random Number Generators

Nowadays, random number generators are regularly used in Monte Carlo simulation and key generation in cryptographic applications. As poor generators will lead to biased results in simulations, the quality assurance of generators has drawn much attention since the thriving of computers. A basic requirement for a good generator is that it passes all commonly known statistical tests of randomness.

The most important character of tests of randomness is their ability to reject poor generators. This ability, referred to as power, is the probability of not making Type II error in testing hypothesis. The power of a test against a specific generator can be estimated. On the other hand, the power of a test against a class of generators is difficult to cope with. Instead of power, we suggest to use a single numeric value called stringency to describe a test’s ability to reject a class of generators. First, we implement a set of canonical generators of a class. The parameters of the generators are chosen using same criteria such that a generator’s ability of passing a test meanly depends on its period. To gauge the stringency of a test, we conduct the test on the canonical generators one by one, from the shortest period to the longest. The stringency of the test is defined as the number of generators it rejects, before the first generator it passes.

 

The MLCG Stringency scale

The linear congruential generator is the most well studied and popular deterministic generator. It was proposed by Lehmer in 1949 and is among the fastest RNGs. The general formula is Xi+1 = a X i + b mod k . As b is non-essential, let us focus on multiplicative linear congruential generator (MLCG) where b = 0. The MLCG Stringency scale consists of 29 canonical MLCGs, with periods varying from roughly 216 to 244. In these generators, we adopted the parameters (a, k)’s published  by L′Ecuyer. These parameters are chosen such that the resulting generators perform well in the spectral test. The actual values of these parameters of the canonical MLCGs are shown below.

Stringency Level a k
16 2469 216 - 15
17 29803 217 - 1
18 21876 218 - 5
19 155411 219 - 1
20 22202 220 - 3
21 1939807 221 - 9
22 1731287 222 - 3
23 422527 223 - 15
24 931724 224 - 3
25 25612572 225 - 39
26 66117721 226 - 5
27 3162696 227 - 39
28 104122896 228 - 57
29 530877178 229 - 3
30 921746065 230 - 35
31 784588716 231 - 1
32 279470273 232 - 5
33 7312638624 233 - 9
34 473186378 234 - 41
35 8094871968 235 - 31
36 45453986995 236 - 5
37 85876534675 237 - 25
38 24271817484 238 - 45
39 541240737696 239 - 7
40 937333352873 240 - 87
41 1319743354064 241 - 21
42 92644101553 242 - 11
43 3663455557440 243 - 57
44 949305806524 244 - 17

 

The LFG Stringency scale

The Lagged Fibonacci generator (LFG) was originally suggested by Mitchell and Moore in 1958. The formula is  Xn =  X n-p+q + X n-p mod m. In a 32-bit computer, m is usually set to 232 for efficiency. The indices p and q are chosen such that xp + xq + 1 is a primitive trinomial. The period of such a generator is 231(2p - 1). This generator is fast and easy-to-implement. The most prominent feature is that a very long period can be achieved by choosing a large p. Twenty seven canonical LFGs with periods of various magnitudes were implemented. The parameters, (p, q)’s are chosen such that the resulting generators are not too difficult to fail.

Stringency Level p q
1 15 8
2 17 11
3 18 11
4 20 17
5 21 19
6 22 21
7 23 14
8 25 18
9 28 15
10 29 27
11 31 18
12 33 20
13 35 33
14 36 25
15 39 25
16 41 21
17 47 26
18 49 27
19 52 31
20 55 31
21 57 35
22 58 39
23 60 49
24 63 32
25 65 33
26 68 35
27 71 36

The stringency of a test against LFGs is defined in the same ways as MLCGs. The measurement is also similar except that the least significant bit (LSB), instead of the MSB, of a number generated is used in the testing. It is because the MSB sequences of LFGs are too difficult to fail.

 

The SHR3 Stringency scale

A shift-register generator computes the next number using the left-shift, right-shift and bitwise exclusive-or operations [Golomb 1982]. Consider a number, w, as a bit sequence. The function left-shift(w, l) shifts w to the left l bits. right-shift(w, r) shifts w to the right r bits. exclusive-or( u, v) conducts a bitwise exclusive-or of u and v. Suppose that the current number of a shift-register generator of parameters (l, r) is W. The next number is computed by the following.

W = exclusive-or( W, left-shift(W, l) );

W = exclusive-or( W, right-shift(W, r) );

If W is treated as a binary vector, the overall computation can be done by multiplying W with a binary matrix [Marsaglia 1985]. The parameters (l, r) are chosen such that the matrix has order 2|W| - 1in the group of nonsingular |W| ´ |W| binary matrices. The theory is also applicable to three-shift generators (SHR3) that have an additional round of left-shift and exclusive-or after the first two rounds [Marsaglia 1999]. SHR3 has the same maximum period, 2|W| - 1, as the two-shift version but scrambles the bits more thoroughly.

Twenty eight canonical SHR3s of various bit lengths were implemented. The parameters, (l1, r, l2)’s, were found using a Maple program that assures the characteristic polynomial of the corresponding binary matrix is primitive. The following table 10 shows the values of these parameters. The definition and measurement of the stringency level of a test against SHR3s are identical to those of MLCGs.

Stringency Level (bit length) Left-shift-1(l1) Right-shift (r) Left-shift-2 (l2)
21 3 7 7
22 3 7 7
23 5 7 3
24 5 7 3
25 7 11 5
26 5 5 11
27 11 11 5
28 11 5 17
29 11 5 17
30 17 17 11
31 17 5 13
32 13 17 5
33 17 7 13
34 7 7 13
35 19 17 11
36 11 11 19
37 13 7 19
38 7 7 17
39 15 5 19
40 7 11 19
41 7 5 19
42 13 11 17
43 15 13 17
44 11 13 25
45 19 13 25
46 19 13 25
47 21 23 25
48 13 13 25

 

Documents and source code of the three stringency scales

API:  rng.readme

Header file: rng.h

Source code: rng.c

A paper on the stringency scales and their applications: Collision.pdf