Cheap and Secure Web Hosting Provider : See Now

[Answers] PRNG bad seeding and von Neumann unbiasing

, , No Comments
Problem Detail: 

Large period PRNGs such as Mersenne Twister require good seeding otherwise the initial output in the sequence may not seem to be high-quality, at least for the first few words (and in the way that is useful in production). For example, Marsaglia talked about seeding methods in his May 2003 Communications of the ACM article [1]. It feels like a chicken/egg situation. You need a source of high-quality random bits in order to seed your generator, so you can create a source of high-quality random bits.

I was wondering:

Is von Neumann unbiasing a legitimate way to defend against poor seeding of large-period PRNGs? In other words, if I apply von Neumann unbiasing to the bitstream output of Mersenne Twister, does the quality of the stream still depend on how I seeded it?

[1] George Marsaglia, "Seeds for random number generators." Communications of the ACM, 46(5):90–93, 2003 (ACM page.)

Asked By : Mayur Patel

Answered By : Yuval Filmus

Von Neumann unbiasing only works if the random source consists of independent samples. Otherwise it is not guaranteed to produce random bits. More generally, in theoretical computer science there exist objects called (randomness) extractors whose job is to extract random bits out of imperfect random sources. Usually they need access to a small number of "high quality" random bits.

In practice, seeding a PRNG is not difficult. There are many legitimate sources of randomness, and using an extractor such as a hash function, you can take a decently sized sample and extract a decently random seed. Once you have a handful of high quality random bits, you can use a PRNG to quickly extract many more seemingly random bits.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/35333

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback