[Python-ideas] Should our default random number generator be secure?
Robert Kern
robert.kern at gmail.com
Thu Sep 10 19:29:22 CEST 2015
On 2015-09-10 00:15, Nathaniel Smith wrote:
> On Wed, Sep 9, 2015 at 3:19 PM, Tim Peters <tim.peters at gmail.com> wrote:
>> The Twister's provably perfect equidistribution across its whole
>> period also has its scary sides. For example, run random.random()
>> often enough, and it's _guaranteed_ you'll eventually reach a state
>> where the output is exactly 0.0 hundreds of times in a row. That will
>> happen as often as it "should happen" by chance, but that's scant
>> comfort if you happen to hit such a state. Indeed, the Twister was
>> patched relatively early in its life to try to prevent it from
>> _starting_ in such miserable states. Such states are nevertheless
>> still reachable from every starting state.
>
> This criticism seems a bit unfair though -- even a true stream of
> random bits (e.g. from a true unbiased quantum source) has this
> property, and trying to avoid this happening would introduce bias that
> really could cause problems in practice. A good probabilistic program
> is one that has a high probability of returning some useful result,
> but they always have some low probability of returning something
> weird. So this is just saying that most people don't understand
> probability. Which is true, but there isn't much that the random
> module can do about it :-)
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.
--
Robert Kern
"I have come to believe that the whole world is an enigma, a harmless enigma
that is made terrible by our own mad attempt to interpret it as though it had
an underlying truth."
-- Umberto Eco
More information about the Python-ideas
mailing list