Validation of Components

www.HEPArts.com

Up to random_bytes Page

Up to PKI Utilities

Random Number Generators

These are results from running tests of the quality of the randomness of Linear-Congruential Random Number Generators, with four different choices of parameters for the recursion equation:

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

The parameters are the Modulus, M, the multiplier, A, and the additive constant, C. The moduli chosen here are all Prime Numbers. The A values have been selected from values in Knuth's Volume-2, which have been tested extensively in the literature to perform well in the Spectral Tests of the randomness distributions.

We intend to combine several LCRNGs together using modular subtraction, as Knuth describes in his Equation-38 on page-108 of Vol-2.

	X(n+1) =  (Ax * X(n))  mod Mx
	Y(n+1) =  (Ay * X(n))  mod My
	Z(n+1) = ( X(n+1) - Y(n+1) ) mod Mx

Since we are subtracting, the C parameters are less relevant, and we set them both to zero in the component generators, X and Y. The parameters, then, are the following:

First  Pair X:  M = (2^31 -   1) = 2147483647, A = 48271
First  Pair Y:  M = (2^31 - 249) = 2147483399, A = 40692

Second Pair X:  M = (2^31 -  61) = 2147483587, A = 32647
Second Pair Y:  M = (2^31 - 171) = 2147483477, A = 16807

Each of the components, X and Y, and the subtracted result, Z, has only 31-bits of information. This is dictated by the size of the modulus. In order to fill out a full 32-bit word, we must merge two by shifting one number up. To be symmetric, we also shift the other number down by the same amount. To be certain of the coverage of the 32-bits, we shift up and down by 3-bits, which lets some of the data spill over both edges. The "merging" is performed as a "Exclusive-OR" (XOR) operation.

In the tests of the component LCRNGs, X and Y, we have to employ the "shuffling" technique. Since each component produces only 31-bits of data, we must merge two results, one shifted up and the other down, to fill out a full 32-bit word. If we were not "shuffling" the second word, we would be combining successive values in the component recursion. This would not be good, because the merging relies on the assumption that the component partial words are independent, which is clearly not true for immediate recursion. Shuffling this second word before merging loosens its dependence on the first word.

Consequently, for the component-tests on the Y-generator itself, we employ "shuffling" on the second Y-values before using them to form the test-values. The Y-values are put into a "deck" of 127, and a simple LCRNG is used at each request to pick one of the "cards" in this deck. The new value of Y is put into this slot, and the old value of Y is merged to form the new test-value. The same procedure is done for the component X-generator tests.

This concern does not exist, of course, in the final combined Z-generator, because the final 32-bit word is the merger of a 31-bit word from the Z-generator of the "First Pair" with one from the "Second Pair". Since all of the generating parameters are different, there are no correlations between these components.

Quality Tests

The results for the final "Combined-Z" generator are shown:

 1.) Frequency    Test PASSED, Chi-squared Probability = 0.772973
 2.) Serial       Test PASSED, Chi-squared Probability = 0.274006
 3.) Gap          Test PASSED, Chi-squared Probability = 0.631027
 4.) Poker        Test PASSED, Chi-squared Probability = 0.562474
 5.) Coupon       Test PASSED, Chi-squared Probability = 0.043532
 6.) Permutation  Test PASSED, Chi-squared Probability = 0.968716
 7.) Runs         Test PASSED, Chi-squared Probability = 0.154201
 8.) Maximum      Test PASSED, Chi-squared Probability = 0.828578
 9.) M-tuple      Test PASSED, Chi-squared Probability = 0.695304
10.) Birthdays    Test PASSED, Chi-squared Probability = 0.817622

Seed time:  0.011177 seconds;  
Test time: 24.797765 seconds; 2.3649e-05 sec/rand.

A Chi-Square-Probability should range uniformly between 0 and 1; any value within the range is acceptable. Values too close to either edge, however, are suspect. A reasonable cut-off for success is being farther from an edge than about one part per thousand, or 0.1%. This is the value that is used to determine whether a test passes or fails.

This file contains all the results of the tests: Component Validity Tests.

These ten passes were performed on a Pentium-4, 2.8 GHz. The Operating System was Fedora Core 4 Linux, which uses a kernel of version-2.6. The machine was running standard stuff, but it was not otherwise loaded. The tests were run overnight, so there was no operator contending for CPU usage.

webmaster@HEPArts.com