5 ms·
It is of course impossible to get true randomness from a deterministic algorithm, but many pseudo-random generators (PRG) are often good enough for practical ap
by ot 13y ago
It is of course impossible to get true randomness from a deterministic algorithm, but many pseudo-random generators (PRG) are often good enough for practical applications, for example statistical simulations.
Bad PRGs can be ruled out by tests like the one in the article, that is, showing that the exhibit some regularities that would be unlikely to get from a truly random source. An infamous example is RANDU [1], whose output is concentrated on low-dimensional subsets.
Smart people have put together batteries of statistical tests to assess the quality of PRG, the most famous being the Diehard test [2]. The idea is that if a PRG passes all the tests it is indistinguishable from a truly random source for all practical purposes.
Good generators such as the widely used Mersenne Twister pass most of its tests. There are even better generators that pass more tests, such as Marsaglia's Xorshift [3], which is faster and simpler than the Mersenne Twister, and surprisingly not very well known.
For anyone interested in PRGs, I strongly recommend reading Marsaglia's original paper [4], it is a good example of how to design a principled PRG and it just requires some elementary linear algebra on finite fields.
[1] http://en.wikipedia.org/wiki/RANDU http://en.wikipedia.org/wiki/RANDU
[2] http://en.wikipedia.org/wiki/Diehard_tests http://en.wikipedia.org/wiki/Diehard_tests
[3] http://en.wikipedia.org/wiki/Xorshift http://en.wikipedia.org/wiki/Xorshift
[4] http://www.jstatsoft.org/v08/i14/paper http://www.jstatsoft.org/v08/i14/paper
- baby 13y agoReminds me of those test for cyphers that test if your cypher gives you something close to a random function. If it does you're good.
- dietrichepp 13y agoThe Diehard tests are great, unfortunately Marsaglia is no longer with us. I recommend the Dieharder tests, which reimplement the Diehard tests but are licensed under the GPL and are actively maintained. http://www.phy.duke.edu/~rgb/General/dieharder.php http://www.phy.duke.edu/~rgb/General/dieharder.php
- DavidPlumpton 13y agoThought I read that the Mersenne Twister has a major vulnerability. It's possible from a small number of samples (<1000) to predict the future values. Hmmm, this is the best link I can find http://b10l.com/?p=24 http://b10l.com/?p=24
- SeanLuke 13y agoOf course it has this "vulnerability": 624 of those values are MT's internal random seed. RNGs have two primary functions: to provide statistically random values (for simulations, say) and to provide unpredictable values (mostly for crypto). These are different goals, and many RNGs are good at one but not the other. That's why we have both RNGs and Crypto RNGs. Like many good RNGs for simulation, Mersenne Twister is not, and never has been, a Crypto RNG. It is explicitly in the first category.
- gjm11 13y agoThere's a paper by Panneton and l'Ecuyer (linked from the Wikipedia article about Xorshift) that seems to indicate that simple Xorshift generators fail some statistical tests very badly. (Not the ones in Marsaglia's Diehard suite -- he tested them with those -- but others.) I think a better approach is another recommended by Marsaglia: take a few different RNGs working on different principles, and just combine them by (say) adding them up. Or, of course, just use something like the Mersenne Twister, which is more complicated than (e.g.) Marsaglia's KISS but there are enough good implementations out there that it doesn't really matter.