6
$\begingroup$

There are many packages out there. In particular, PractRand gives out an opinion on a number of them, but it's only an opinion. Is there conventional wisdom about which set of set of statistics tests should be used to to test out a random number generator?

Update1: Given @usεr11852's comment, answers may go towards tests for PRNG or CSPRNG. I'll consider it answered if any current formal recommendations exist for either one.

Update2: Given @usεr11852's and @DW's comment, answers should assume tests for PRNG (and not for CSPRNG). (If that's possible at this stage.)

| cite | improve this question | |
$\endgroup$
  • 3
    $\begingroup$ Just to be clear, are we talking about cryptographically secure pseudo-random number generators (PRNGs) or your "standard" PRNGs? Are we looking to MCMC or to create cyphertext? We do not test a bulldozer and a WRC car the same way... Very relevant thread from Crypto.SE here $\endgroup$ – usεr11852 Sep 23 '18 at 13:13
  • $\begingroup$ Good point. So, after a first consideration of the issue, I'd like to separate the two things completely. So I'm interested in tests for PRNG, CSPRNG separately. Question edited to account for this. Thanks! $\endgroup$ – user45491 Sep 23 '18 at 13:25
  • 1
    $\begingroup$ Usually TestU01's is considered a standard "statistical test suite" that any aspiring PRNG has to pass - the BigCrush version of it is the most significant test. I strongly suspect that if a PRNG does not pass BigCrush it would be tricky to explain the reason of its existence. The "compact" (213-page) version of [TestU01] manual gives more details about it. ;) $\endgroup$ – usεr11852 Sep 23 '18 at 13:37
  • 1
    $\begingroup$ "The conventional wisdom about which set of set of statistics tests should be used to to test out a random number generator" is that a PRNG has to pass both PractRand and TestU01. Modern PRNG, like the PCG, explicitly test both. (I wrote that almost immediately after my comment but I did not have time write a proper answer and I think the current ones cover the main points. Crypto.SE is your friend!) $\endgroup$ – usεr11852 Sep 23 '18 at 14:08
  • 3
    $\begingroup$ Please pick one to ask about (CSPRNG or non-crypto PRNG). Asking about both in the same question is too broad. The answers for the two are very different, so if you really want to ask about both, you should post them separately as two separate questions. $\endgroup$ – D.W. Sep 23 '18 at 16:10
9
$\begingroup$

In addition to the Dieharder suite that Sephan Kolassa mentioned, other well known test suites include TestU01 and the NIST Statistical Test Suite (STS).

The PractRand library you mentioned rates Dieharder and STS as "bad" and TestU01 as "good". But, unlike the other test suites, PractRand is not as well known, and there do not seem to be any academic papers or external review. So, one would have to use their own judgement in trusting these comparisons (there's a little bit of information here on the PractRand webpage).

I'd recommend having a look at crypto.stackexchange.com. For example, some relevant threads here and here.

An important thing to note is that scientific and cryptographic applications have different requirements for pseudorandom number generators. Statistical randomness is necessary for both. But, it's not sufficient for cryptographic applications, which also need resistance to attacks that try to exploit the internal workings of the random number generator. This cannot be verified by statistical tests, and requires cryptanalysis.

References

  • L'Ecuyer et al. (2007). TestU01: A C library for empirical testing of random number generators.

  • Bassham et al. (2010). A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications.

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

In 1995, the Diehard suite of tests was distributed. This is no longer state of the art - one limitation is that Diehard only uses about 10 million random numbers in each test, but modern uses of random numbers may consume many more, so tests should base their conclusions on larger samples.

A successor to the Diehard suite is the Dieharder suite. I believe this is state of the art, but (disclaimer) I am not an expert in random number testing, so an answer from anyone who actually is an expert and could actually back their reply up with literature would be much appreciated.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Dieharder has been recently considered bad quality --- meaning not well able to distinguish good from bad generators. It's not clear when this opinion was written, but looking inside the package it might have been August 2018 --- inferring this from last modification dates on the file. PractRand considers gjrand ``very good,'' the only one considered very good. But it doesn't expose any rationale for the rating. $\endgroup$ – user45491 Sep 23 '18 at 13:01
  • 1
    $\begingroup$ @user45491: That seems to be the opinion of the author of a competing package, and indeed the opinion is not backed by examples or proofs. Considering it's a decision problem, a test is bad quality if it has many false positives or false negatives, so a counterexample should really be easy to give. $\endgroup$ – MSalters Sep 24 '18 at 7:26

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.