I need to test a random number generator which produces numbers randomly. How to make sure the numbers generated are random.
12 Answers
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.
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.
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.
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).
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).
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.
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.
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,
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/
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−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.
Related