How to test a random generator

问题:

I need to test a random number generator which produces numbers randomly. How to make sure the numbers generated are random.

回答1:

Use chi-square testing. What language are you using? I can offer a C++ example. Basically

• Place random numbers in buckets (many times).
• The number of buckets minus one is the degrees of freedom.
• Compare the bucket tallies against "expected" tallies, yielding a chi-square result.
• Use a chi-square calculator to see the probability of getting those results.

回答2:

You can only test statistical randomness anyway, and that does not prove whether the number sequence is cryptographically strong. Statistically testing a PRNG requires quite a lot (10 or even 100Gbytes) of the generated bits.

Dieharder is a very good testing suite.

http://www.phy.duke.edu/~rgb/General/dieharder.php

And TestU01 is also well-known.

http://www.iro.umontreal.ca/~simardr/testu01/tu01.html

回答3:

Here is a detailed explanation of how to start. The preliminary test for any RNG is the Monobit test used by the NIST which simply counts the number of 1s and 0s. http://csrc.nist.gov/groups/ST/toolkit/rng/stats_tests.html

A note about testing a Random Number Generator: We actually don't need too many RNG tests because many "subsume" one another.

That said, described here is a simple effective new Ordered Frequency Test for bits. This test subsumes any frequency test that expects 50-50 because it is more stringent.

Definitions: t= tosses / trials b=bins / urns s=sessions of tosses n=sets of sessions

Because coin tosses are usually not 50-50, this new test can be utilized with great effectiveness using a pool of 40,000,000 bits.

When coins are flipped 100 times, the expected values are 53.9795 of one and 46.0205 of the other, sometimes more heads, sometimes more tails. 50-50 is not the expected value of the ordered bins, so this test is superior to any frequency test that instead expects 50-50.

Step 1: Choice of sample size: 100 tosses / bits.

Step 2: Choice of number of Sessions: 50 sessions is never sufficient, even with huge sample sizes in the millions. 400 is usually enough. 2000 converges well, so 2000 different samples of 100 tosses are used. Minimal gain occurs above 2000.

Expected values for 2000 sessions of 100 tosses: 50-50 159.1784748 (Notice that 50-50 occurs a mere 7.96% of the time.) 51-49 312.1146564 52-48 294.1080416 53-47 266.362 54-46 231.8335926 55-45 193.8971865 56-44 155.8102392 57-43 120.2745706 58-42 89.16907819 59-41 63.47629295 60-40 43.37546685 61-39 28.4429291 62-38 17.89152 63-37 10.79171042 64-36 6.238957586 65-35 3.455422663
66-34 1.832421109 67 or more 1.747439674

The equation to obtain the exact percentages for bins b=2 and tosses t=100 is: For 100-0, the odds are 1 / (2^99) = 1 / (2^(t-1)) Then, building up from there, for 99-1 previous multiplied by 100 (t) divide by 1 for 98-2 previous multiplied by 99 (t-1) divide by 2 for 97-3 previous multiplied by 98 (t-2) divide by 3 ... skip ... for 51-49 previous multiplied by 52 (t-48) divide by 49 for 50-50 previous multiplied by 51 (t-49) divide by 50, then divide again by 2.

This equation works with any number of tosses.

Step 3: A chi-square is taken on these 18 values with 17 degrees of freedom giving a resulting p value.

p values above 0.999 are close to perfection. Can an RNG be too close to perfection too often? Yes, being too predictable. Under 0.001 is where definite problems usually occur. One test suite considers 300 zeroes to the right of the decimal as infinitesimally bad and 10-14 in a row as quite bad. Some consider 6 zeroes bad enough to qualify as a definite clear failure. Some, for the sake of safety, consider 1 or 2 zeroes enough and they are in error. So, instead of a single p value for a single set sometimes providing a p value below 0.01 for an excellent RNG, many sets of sessions are taken.

Step 4: The p values are fed to a 0-1.0 straight line Kolmogorov-Smirnov test. Different experts recommend the number of inputs to the K-S test to be from 10 to 1000. 100 is not quite enough. 200 is fine. 500 is slightly aggressive.

Here is pseudocode to obtain the K-S maximum difference:

Set low := 0;  Set n := 200;  
Set ansForward := 0; Set ansBack := 0;

sort( pval [n] );
for (j := 0; j < n; j := j+1)   
 {  Set Kback := pval [ j ] - low;
    Set low := low +1 / n;    { Ranges from 0 to 1 }
    Set Kforward := low - pval [ j ];  
    if (Kforward > ansForward) Set ansForward := Kforward;
    if (Kback > ansBack) Set ansBack := Kback;
   }
{ Separate analysis can perhaps be made here on ansForward and ansBack.  Someone like Peter Brand might also examine and magnify the bottom 5% and the top 5%. }
if (ansForward > ansBack)
      return ansForward;
else
      return ansBack;   ∎

The K-S answer is not a p value and should not exceed 0.115 for 200 p values. 0.03 to 0.08 is normal for a good RNG. 0.115 to 0.13 is suspect.

The K-S test is very simple It is also quite effective.

Shown above is a superior new Ordered Frequency Test. Any RNG which fails this test should not be tested further and immediately replaced. But, what next?

The OFTest does not subsume the LOR test. Recommended is the Length Of Runs test with sample size 200,000 with 15 degrees of freedom fed into the K-S test 200 times. (Note that the expected total of the smallest LOR bin for "more than j" is equal to the jth bin.)

And then what? For many games, these two tests are all you need. There are a propensity of choices from NIST, Diehard, Dieharder, Crusher. (Note: The Diehard Overlapping Sums test is both inferior and faulty, not a faithful interpretation of Marsaglia's original Fortran code.)

Results from a few RNGs with n=200.

1. LCG 134775813x + 1 mod 2^31 seed=11111: High bit: OFT KS: 0.0841 Pass. LOR KS: 0.04786 Pass. Monobit of first 200,000: -189 Pass. Bit 16: OFT KS: 0.5477 Fail. Monobit of first 200,000: 114 Pass. All bits from 0 to 15 fail the OFT, yet pass the Monobit test.

2. The oft maligned LCG Randu: 65539x + 0 mod 2^31 seed=11111:
   High bit: OFT KS: 0.03567 LOR KS: 0.07709. Monobit of first 200,000: -165 Bit 18: OFT KS: 0.15143 Monobit of first 200,000: +204 All bits from 0 to 17 fail the OFT.

3. LCG 69069x + 1 mod 2^32 seed=11111: High bit: OFT KS: 0.05547 LOR KS: 0.0456 Monobit of 200,000: -290 Bit 17: OFT KS: 0.1467 Monobit of 200,000: -193 All bits from 0 to 13 fail the OFT.

4. LCG 3141592653x + 2718281829 mod 2^35 seed=11111: High bit: OFT KS: 0.02868 LOR KS: 0.06117 Monobit of 200,000: -69 Bit 16: OFT KS: 0.240 Monobit of 200,000: -13 All bits from 0 to 15 fail the OFT.

5. LCG 23x + 0 mod 2^27 seed=11111: High bit: OFT KS: 0.5368 Monobit of 200,000: -235 All bits fail the OFT.

Notice that the low bits of any and every LCG should be discarded from the returned result.

A note about 2^35: This is the minimum period and significance for any RNG because coin flips and craps runs and such things can happen 30 times in a row, but 35 just isn't expected to happen. A period of 2^32 is insufficient, too small for real life situations.

LWAP

回答4:

How to make sure the numbers generated are random.

You can't make sure, there is no way to distinguish with certainty any function from a random number generator using a finite number of tests. But you can do Statistical Analysis:

So, if it is impossible to definitively prove randomness, what can we do instead? The pragmatic approach is to take many sequences of random numbers from a given generator and subject them to a battery of statistical tests. As the sequences pass more of the tests, the confidence in the randomness of the numbers increases and so does the confidence in the generator. However, because we expect some sequences to appear nonrandom (like the ten rolls of six on our die), we should expect some of the sequences to fail at least some of the tests. However, if many sequences fail the tests, we should be suspicious. This is also the way you would intuitively test a die to see if it is loaded: Roll it many times, and if you see too many sequences of the same value coming up, you should be suspicious.

See the section on Charmaine Kenny's study for more details on the tests you could run.

回答5:

It's a very difficult thing.

You may try ENT from Fourmilab and compare it with the results against their RNG, HotBits. You may also like to review Random.org.

This also looks interesting: Diehard tests (I've not worked with it though).

回答6:

You cannot ensure the numbers are random simply because random numbers are, well, random.

The chances of getting a string of one million consecutive 9's is the same as getting any other specific one-million-long sequence. The one thing you can check for is correct distribution over a large sample set. Run a sizeable test and work out the relative occurrences of each possible outcome.

Over a large enough sample, they should be roughly the same.

One other possibility is to test for non-repeatability. Ideally, random numbers should not depend on the numbers that came before. Very simple (linear congruential) PRNGs will most likely give you the same sequence of numbers eventually but over a large enough set that you probably won't care (unless you're serious about randomness).

回答7:

Show it to a room full of developers.

回答8:

Often if you have your generator draw dots at random locations in a bitmap, any nonrandomness will easily be discernable to the eye as clumping, banding or lines.

回答9:

Create a log file which will contains the random number for atleast 500 instances and audit it for randomness. Also have a look at below link,

http://burtleburtle.net/bob/rand/testsfor.html

回答10:

It depends how severe your requirement for randomness is. If it is not too severe, what I do is generate a large number of random numbers, find their frequencies and then use the frequencies to plot a graph using a spreadshhet like that in Open Office. If the distribution looks OK, then I'm good to go.

回答11:

There is a good tool for this puprose: http://www.phy.duke.edu/~rgb/General/dieharder.php

for example you can test build-in urandom

cat /dev/random | dieharder -a -g 200

Or write your own script that will create a file with random numbers

dieharder -a -g 202 -f random.txt

回答12:

Unless you have access to the random number generator and can use it to generate numbers at will, you can't test if a sequence of numbers is random. Think about it: you have a random number generator. Let's say it's a uniform random number generator, generating random integers in the range [0,9]. Given a sequence:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9

can you tell if it is random? There is a finite probability 10⁻¹⁰, that our uniform random number generator will generate this exact sequence. In fact, given any length-10 sequence, we have the same probability of our uniform random number generator generating that sequence. Hence, by definition, you can't determine if a given sequence is random.

If you do have access to the generator itself, and can use it to generate multiple sequences, then it makes sense to "check for randomness". For this, I would look at Diehard tests. There are various implementations.

回答13:

You can't generate true randomness by any algorithm, thus try to visualize your outputs and check for patterns with your own eyes. None random generator (by algorithm) would create some patterns that you can judge them yourself. Here is one of demonstration of that idea: http://www.alife.co.uk/nonrandom/