patternMinor
What makes a pseudorandom generator, a high quality one?
Viewed 0 times
qualitywhathighmakesgeneratoronepseudorandom
Problem
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?
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?
Solution
There are several criteria for the quality of a PRNG:
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.
- 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.
Context
StackExchange Computer Science Q#80412, answer score: 8
Revisions (0)
No revisions yet.