[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