[Python-ideas] Should our default random number generator be secure?
Tim Peters
tim.peters at gmail.com
Thu Sep 10 19:48:12 CEST 2015
[Robert Kern <robert.kern at gmail.com>]
> The MT actually does have a problem unique to it (or at least to its family
> of Generalized Feedback Shift Registers) where a state with a high
> proportion of 0 bits will get stuck in a region of successive states with
> high proportions of 0 bits. Other 623-dimensional equidistributed PRNGs will
> indeed come across the same states with high 0-bit sequences with the
> frequency that you expect from probability, but they will be surrounded by
> states with dissimilar 0-bit proportions. This problem isn't *due* to
> equidistribution per se, but I think Tim's point is that you are inevitably
> due to hit one such patch if you sample long enough.
Thank you for explaining it better than I did. I implied MT's "stuck
in zero-land" problems were _due_ to perfect equidistribution, but of
course they're not. It's just that MT's specific permutation of the
equidistributed-regardless-of-order range(1, 2**19937) systematically
puts integers with "lots of 0 bits" next to each other.
And there are many such patches. But 2**19337 is so large you need to
contrive the state "by hand" to get there at once. For example,
>>> random.setstate((2, (0,)*600 + (1,)*24 + (624,), None))
>>> random.random()
0.0
>>> random.random()
0.0
>>> random.random()
0.0
>>> random.random()
0.0
>>> random.random()
0.0
>>> random.random()
0.0
>>> random.random()
0.0
>>> random.random()
0.0
>>> random.random()
0.0
>>> random.random()
0.0
>>> random.random()
0.0
>>> random.random()
0.0
That's "impossible" ;-) (1 chance in 2***(53*12)) of seeing 0.0
twelve times in a row)
More information about the Python-ideas
mailing list