[Python-ideas] Should our default random number generator be secure?

[Tim Peters]

[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)