[Python-ideas] Should our default random number generator be secure?
Robert Kern
robert.kern at gmail.com
Mon Sep 14 23:19:09 CEST 2015
On 2015-09-14 21:56, Sturla Molden wrote:
> On 14/09/15 22:45, Robert Kern wrote:
>> On 2015-09-14 20:07, Sturla Molden wrote:
>>> On 14/09/15 19:15, M.-A. Lemburg wrote:
>>>
>>>> I am well aware that MT doesn't satisfy all empirical tests
>>>> and also that it is not a CSPRNG
>>>
>>>> However, it has been extensively studied and it is proven to be
>>>> equidistributed which is a key property needed for it to be used as
>>>> basis for other derived probability distributions (as it done by the
>>>> random module).
>>>
>>> And with this criterion, only MT and certain PCG generators are
>>> acceptable.
>>> Those are (to my knowledge) the only ones with proven equidistribution.
>>
>> Do not confuse k-dimensional equidistribution with "equidistribution".
>> The latter property (how uniformly a single draw is distributed) is the
>> one that the derived probability distributions rely upon, not the
>> former.
>
> Yes, there was something fishy about this. k-dimensional equidistribution
> matters if we simulate a k-dimensional tuple, as I understand it.
Yeah, but we do that every time we draw k numbers in a simulation at all. And we
usually draw millions. In that case, perfect k=623-dimensional equidistribution
is not really any better than k=1, provided that the PRNG is otherwise good.
The requirement for a good PRNG for simulation work is that it be *well*
distributed in reasonable dimensions, not that it be *exactly* equidistributed
for some k. And well-distributedness is exactly what is tested in TestU01. It is
essentially a collection of simulations designed to expose known statistical
flaws in PRNGs. So to your earlier question as to which is more damning, failing
TestU01 or not being perfectly 623-dim equidistributed, failing TestU01 is.
--
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