Bad Generators

www.HEPArts.com

Up to random_bytes Page

Up to PKI Utilities

Bad Random Number Generators

Overview

Some Random Number Generators are not very good at producing a stream of numbers which appear to come in random order. Even ones that look random to the eye can have subtle patterns in long sequences. The Randomness Tests have been designed to ferret out such failures.

Linear-Congruential

We will start with the very common and well studied Linear-Congruential Random Number Generator (LCRNG), which is defined by the following recursion equation:

	X(n+1) = (A * X(n) + C) mod M

The parameters are the the multiplier, A, the additive constant, C, and and Modulus, M. Each successive number, X(n+1), is derived from the previous number, X(n). The choice of a good set of parameters is essential. We show a couple of bad sets of parameters.

If we choose the modulus to be a power of 2 (a machine word in particular), then any choice of the other parameters yields unsatisfactory results. We show some of the failed Quality tests for a few such choices. Only the high-order bits of the resulting generation are reasonably random. The low-order bits are woefully bad.

Modulus = (2^32) = 4294967296
A                =      48271

Using Full Words

Processed 10,000,000 Random Numbers.

 1.) Frequency    Test FAILED, Chi-squared Probability = 1.000000
 2.) Serial       Test FAILED, Chi-squared Probability = 1.000000
 3.) Gap          Test FAILED, Chi-squared Probability = 0.000000
 4.) Poker        Test PASSED, Chi-squared Probability = 0.528199
 5.) Coupon       Test FAILED, Chi-squared Probability = 0.000000
 6.) Permutation  Test FAILED, Chi-squared Probability = 0.000000
 7.) Runs         Test PASSED, Chi-squared Probability = 0.324876
 8.) Maximum      Test FAILED, Chi-squared Probability = 0.000000
 9.) M-tuple      Test FAILED, Chi-squared Probability = 1.000000
10.) Birthdays    Test FAILED, Chi-squared Probability = 0.000000

We also show results by taking only the top half word or the top byte and ignoring the lower bits. This gets improved results, but the whole approach is unacceptable.

Using Top Half-Words

There just is not enough randomness in the low-order bits. What if we take only the top 16-bits from two passes to build a 32-bit random word? Let's see.

 1.) Frequency    Test FAILED, Chi-squared Probability = 1.000000
 2.) Serial       Test PASSED, Chi-squared Probability = 0.117371
 3.) Gap          Test PASSED, Chi-squared Probability = 0.029553
 4.) Poker        Test PASSED, Chi-squared Probability = 0.749371
 5.) Coupon       Test PASSED, Chi-squared Probability = 0.285663
 6.) Permutation  Test PASSED, Chi-squared Probability = 0.989890
 7.) Runs         Test PASSED, Chi-squared Probability = 0.012405
 8.) Maximum      Test PASSED, Chi-squared Probability = 0.989399
 9.) M-tuple      Test PASSED, Chi-squared Probability = 0.924522
10.) Birthdays    Test PASSED, Chi-squared Probability = 0.825255

As we can see, it fails the Frequency test completely. It has some spikes and some deep troughs in the Chi-Squared distribution .

Using Top Byte Only

OK, let's try taking only the top byte of each generated word, concatenating four of them together to get the full 32-bits.

 1.) Frequency    Test PASSED, Chi-squared Probability = 0.565858
 2.) Serial       Test PASSED, Chi-squared Probability = 0.391258
 3.) Gap          Test PASSED, Chi-squared Probability = 0.244219
 4.) Poker        Test PASSED, Chi-squared Probability = 0.168903
 5.) Coupon       Test PASSED, Chi-squared Probability = 0.107363
 6.) Permutation  Test PASSED, Chi-squared Probability = 0.908751
 7.) Runs         Test PASSED, Chi-squared Probability = 0.666203
 8.) Maximum      Test PASSED, Chi-squared Probability = 0.875953
 9.) M-tuple      Test FAILED, Chi-squared Probability = 1.000000
10.) Birthdays    Test PASSED, Chi-squared Probability = 0.084279

This mostly succeeds now. However, it fails the M-tuple test. In ten independent runs , it fails the M-tuple test everytime. OK, we have to give up on this.

Prime Number Modulus

Let us move on to choosing a Prime Number for the Modulus, which makes all of the bits of the result valid.

Modulus = (2^31 -   1) = 2147483647
A                      =      48271

Processed 10,000,000 Random Numbers.

31-bit Words

Just to show the kind of problems that result from missing a bit, we run on a good set of parameters, but try to use the word directly, which has only 31-bits of the data.

We display how often the 8-th bit is ON in each byte of the output words:

High-bit on             0               times; average = 0
Eighth-bit(3) on        0               times; average = 0
Eighth-bit(2) on        5.00179e+06     times; average = 0.500179
Eighth-bit(1) on        4.99999e+06     times; average = 0.499999
Eighth-bit(0) on        5.00116e+06     times; average = 0.500116

And, these are the results:

1.) Frequency    Test FAILED, Chi-squared Probability = 1.000000
2.) Serial       Test FAILED, Chi-squared Probability = 1.000000
3.) Gap          Test FAILED, Chi-squared Probability = 0.000000
4.) Poker        Test PASSED, Chi-squared Probability = 0.667942
5.) Coupon       Test PASSED, Chi-squared Probability = 0.989316
6.) Permutaion   Test FAILED, Chi-squared Probability = 1.000000
7.) Runs         Test FAILED, Chi-squared Probability = 0.000000
8.) Maximum      Test FAILED, Chi-squared Probability = 1.000000
9.) M-tuple      Test PASSED, Chi-squared Probability = 0.351330

Merging Two 31-bit Words

We use all the same parameters, but now we merge two of these 31-bit words, generated in succession, to form the full 32-bit word. We show three independent runs:

1.) Frequency    Test PASSED, Chi-squared Probability = 0.850551
2.) Serial       Test PASSED, Chi-squared Probability = 0.005881
3.) Gap          Test PASSED, Chi-squared Probability = 0.195784
4.) Poker        Test PASSED, Chi-squared Probability = 0.605753
5.) Coupon       Test PASSED, Chi-squared Probability = 0.172979
6.) Permutaion   Test PASSED, Chi-squared Probability = 0.214932
7.) Runs         Test PASSED, Chi-squared Probability = 0.798218
8.) Maximum      Test PASSED, Chi-squared Probability = 0.848371
9.) M-tuple      Test PASSED, Chi-squared Probability = 0.376109

1.) Frequency    Test PASSED, Chi-squared Probability = 0.071785
2.) Serial       Test PASSED, Chi-squared Probability = 0.172783
3.) Gap          Test PASSED, Chi-squared Probability = 0.486854
4.) Poker        Test PASSED, Chi-squared Probability = 0.420868
5.) Coupon       Test PASSED, Chi-squared Probability = 0.514283
6.) Permutaion   Test PASSED, Chi-squared Probability = 0.017437
7.) Runs         Test PASSED, Chi-squared Probability = 0.807945
8.) Maximum      Test PASSED, Chi-squared Probability = 0.446131
9.) M-tuple      Test PASSED, Chi-squared Probability = 0.879226

1.) Frequency    Test PASSED, Chi-squared Probability = 0.152518
2.) Serial       Test PASSED, Chi-squared Probability = 0.195991
3.) Gap          Test PASSED, Chi-squared Probability = 0.329541
4.) Poker        Test PASSED, Chi-squared Probability = 0.593656
5.) Coupon       Test PASSED, Chi-squared Probability = 0.092515
6.) Permutaion   Test PASSED, Chi-squared Probability = 0.450394
7.) Runs         Test PASSED, Chi-squared Probability = 0.331486
8.) Maximum      Test PASSED, Chi-squared Probability = 0.360640
9.) M-tuple      Test PASSED, Chi-squared Probability = 0.288691

Everything looks good now. XOR-ing two words shifted in opposite directions cleans up the lack of randomness.

Lagged-Fibonacci

Another very common type of generator is a Lagged Fibonacci Random Number Generator (LFRNG), which is defined by the following recursion equation:

	X(n+1) = (X(n-j) + X(n-k)) mod M

These are improvements on the original generator of the Fibonacci Series,

	X(n+1) = (X(n) + X(n-1)) mod M

Using this original equation as the generator turns out to produce very bad results.

For a few actual tests, we choose j=0 and k=3, and we use the word-size as the modulus:

	X(n+1) = (X(n) + X(n-3)) mod M

Processed 10,000,000 Random Numbers.

 1.) Frequency    Test PASSED, Chi-squared Probability = 0.033509
 2.) Serial       Test PASSED, Chi-squared Probability = 0.346506
 3.) Gap          Test PASSED, Chi-squared Probability = 0.695136
 4.) Poker        Test PASSED, Chi-squared Probability = 0.694450
 5.) Coupon       Test PASSED, Chi-squared Probability = 0.612935
 6.) Permutation  Test PASSED, Chi-squared Probability = 0.437847
 7.) Runs         Test PASSED, Chi-squared Probability = 0.421978
 8.) Maximum      Test PASSED, Chi-squared Probability = 0.789680
 9.) M-tuple      Test PASSED, Chi-squared Probability = 0.248623
10.) Birthdays    Test FAILED, Chi-squared Probability = 0.000000

It does well on all the tests except the Birthday Spacings test. It turns out that all Lagged-Fibonacci generators fail this test consistently.

This is another test, with j=24 and k=55, and with the word-size as the modulus.

Processed 10,000,000 Random Numbers.

 1.) Frequency    Test PASSED, Chi-squared Probability = 0.492595
 2.) Serial       Test PASSED, Chi-squared Probability = 0.627233
 3.) Gap          Test PASSED, Chi-squared Probability = 0.568029
 4.) Poker        Test PASSED, Chi-squared Probability = 0.502721
 5.) Coupon       Test PASSED, Chi-squared Probability = 0.019600
 6.) Permutation  Test PASSED, Chi-squared Probability = 0.239875
 7.) Runs         Test PASSED, Chi-squared Probability = 0.140632
 8.) Maximum      Test PASSED, Chi-squared Probability = 0.554401
 9.) M-tuple      Test PASSED, Chi-squared Probability = 0.311031
10.) Birthdays    Test FAILED, Chi-squared Probability = 0.000000

webmaster@HEPArts.com