1
$\begingroup$

I am using the NIST randomness test suite which checks whether a bit sequence is random over 15 different tests. I have problems in verifying if this suite works fine. The situation is that if I input, for example, 10000 sequences of the same length (e.g., 1000) and generated by rand function of MATLAB, sometimes it passes the basic tests I use, i.e., frequency, runs, block frequency, cumulative sums. However, sometimes it fails the basic frequency test and cumulative sums test in terms of p-value of p-values but not in terms of proportion.

I have two questions. The general one is how can I generate uniformly distributed random bits from MATLAB? The second is, why the problem mentioned above happens in NIST randomness suite, can anyone help me to verify if it works fine?

For reference document : http://csrc.nist.gov/groups/ST/toolkit/rng/documents/SP800-22rev1a.pdf

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Maybe 10000 is just not enough to establish a significant decision? It does not seem large, especially if you compare it with the number of all possible 1000-bit words. $\endgroup$ – user88 Sep 18 '13 at 12:59
  • $\begingroup$ I don't remember details of the NIST tests, but why are you expecting that the generator passes them? It's one for numerics, not a cryptographic quality one. You can check which PRNG your Matlab version uses ("recently" they switched to Mersenne Twister) and look at corresponding dieharder results. For random bits just use rand()>0.5. $\endgroup$ – Quartz Sep 18 '13 at 16:01
  • $\begingroup$ @mbq I know that it is not the best case but the manual does not specify the number of bit sequence except the minimum value of 55; therefore, I think 10000 should be OK. $\endgroup$ – deliberately Sep 19 '13 at 8:42
  • $\begingroup$ @Quartz Why I expect it to pass all the tests is that there are even papers published with less bit lengths and their whole idea is that we made it pass all the tests and theoretically in my case it should does that, at least for the random generated bits. About your suggestion I do not know how to check dieharder results. Can you please inform me about it? $\endgroup$ – deliberately Sep 19 '13 at 8:43
  • $\begingroup$ I don't think so... 10 000 may be OK for 55-bit words but IMO the required number of test should grow exponentially with the word length. By the way, why can't you use like 100-bit words? 1000 seems just huge. $\endgroup$ – user88 Sep 19 '13 at 10:33
3
$\begingroup$

Keep in mind: Dilbert on random numberssource

Sounds like you are repeating the experiment. In that case, even for truly random numbers you have to expect a number of failures that corresponds to the specified p-value.

What about getting some truly random numbers (e.g. random.org, or HotBits or the like) and trying those to get a baseline against which you can compare the matlab generator? As you'll need many random bits (far more than the free allowance) you'll probably write them and ask nicely.

I also like the discussion of testing for randomness at random.org, which besides the general ideas and caveats also links to a report on their random number generation using the NIST tests. HotBits of cousre has a random number statistics page as well.

By the way, browsing through the report I read that for the NIST tests 5.5e6 random numbers are recommended for the testing. If I understand your setup correctly, you were running with 1e4, so a factor 50 below the recommendation.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ As you said I expect some percentage of failures as relevant to my confidence value. The case here is not directly related to that. What fails is the P_value of P_values, which is checked for uniformity of P_values in [0,1]. In addition, the recommendations are 1e06 bit lengths and at least 55 of them. However, this is the ideal case and 7 of the tests can be used even for bit length of 100 according to the recommendations... $\endgroup$ – deliberately Sep 19 '13 at 8:53
  • $\begingroup$ However, as you have pointed out the problem is still about the length of my bit sequence since if I increase the length of the bit sequence for the same bit sequences then they pass the tests. That is really interesting to me. For the websites you mentioned, do you where exactly I can write and since I really cannot read the details of these random number generations due to the strict time constrints I have, can you tell me why they are better as a short summary? $\endgroup$ – deliberately Sep 19 '13 at 8:54
  • $\begingroup$ @Onur: I don't know anything about those true random number generators that isn't written on those web pages, sorry. But I noticed that the report linked at random.org has a discussion whether it is at all appropriate to use the same tests for true random number generators or pseudo random number generators. $\endgroup$ – cbeleites Sep 19 '13 at 10:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.