7
$\begingroup$

Reading this answer to this SO question: Why do we not combine random number generators?, it talks about

very high-quality PRNG (Pseudo Random Number Generator)

so it makes me wonder what constitutes a high-quality PRNG, I assume you can sum it up as it being "more random", but

  • Question1: Which qualities of a PRNG are used to describe how 'random' or 'good' it is?

  • Question2: If you have a 'bad quality' PRNG, is there a way to make it better quality?

$\endgroup$
  • $\begingroup$ Relevant stackoverflow.com/questions/2130621/… $\endgroup$ – adrianN Aug 25 '17 at 8:31
  • 2
    $\begingroup$ You also need to distinguish mundane PRNGs from cryptographically secure RNGs. $\endgroup$ – adrianN Aug 25 '17 at 8:32
  • 1
    $\begingroup$ A PRNG is 'better' if it is harder to distinguish its output from completely random bits. $\endgroup$ – Yuval Filmus Aug 25 '17 at 10:54
8
$\begingroup$

There are several criteria for the quality of a PRNG:

  • How fast it is. This includes how fast it is to setup it, and how fast it is to produce a single bit (amortized).
  • How difficult it is to guess the next bit given all previous bits.
  • How difficult it is to distinguish between output of the PRNG and truly random bits.

The last two criteria are strongly related.

If you have a bad quality PRNG, you can often make it better by hardness amplification. Take several copies of the PRNG (using different random keys) and XOR them together. In many (though not all) cases this will significantly improve its quality.

$\endgroup$
  • $\begingroup$ Just another question: Why use a PRNG which will cause the same sequence if the same seed is used twice, and not just get a new seed (cpu clock for example) each time a new random number is necessitated? wouldn't this approach be more random? $\endgroup$ – Jose Aug 26 '17 at 21:49
  • 1
    $\begingroup$ @Jose This is by design. In many cases you want to be able to generate the exact same sequence many times. Two examples are Monte Carlo experiments (which should be repeatable) and cryptography (where we want two users to possess the same random sequence, used as a key). $\endgroup$ – Yuval Filmus Aug 26 '17 at 21:54
  • $\begingroup$ Monte Carlo experiments rarely needs a cryptographic PRNG. $\endgroup$ – Xavier Combelle Sep 1 '17 at 12:45
2
$\begingroup$

There are practical considerations: How easy to use? How fast? How easy is it to produce a different sequence of random numbers? How easy is it to replay the random numbers (for example, if you generated 10 billion random numbers, can you generate the exact same 10 billion random numbers again?)

The big question: Do the numbers generated behave like a sequence of random numbers? The first PRNG that I ever used had the bizarre property that of two consecutive values, the second was larger with probability about 0.6. Not very random. So you can run all kinds of statistical tests and check if your random number generator behaves in a random way. The more it behaves like random, the better.

And then comes cryptographical randomness. If I give you the last n random numbers, and complete knowledge how the random number generator behaves, can you predict the next random number? If yes, that makes it unsuitable in situations where you have adversaries.

$\endgroup$

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.