[Python-ideas] Should our default random number generator be secure?
robert.kern at gmail.com
Tue Sep 15 13:21:57 CEST 2015
On 2015-09-15 04:53, Steven D'Aprano wrote:
> On Mon, Sep 14, 2015 at 10:19:09PM +0100, Robert Kern wrote:
>> 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.
> I'm confused here. Isn't "well-distributed" a less-strict test than
> "exactly equidistributed"? MT is (almost) exactly k-equidistributed up
> to k = 623, correct? So how does it fail the "well-distributed" test?
k=623 is a tiny number of dimensions for testing "well-distributedness". You
should be able to draw millions of values without detecting significant
Perfect k-dim equidistribution is not a particularly useful metric on its own
(at least for simulation work). You can't just say "PRNG A has a bigger k than
PRNG B therefore PRNG A is better". You need a minimum period to even possibly
reach a certain k, and that period goes up exponentially with k. Given two PRNGs
that have the same period, but one has a much smaller k than the other, *then*
you can start making inferences about relative quality (again for simulation
work; ChaCha20 has a long period but no guarantees of k that I am aware of, but
its claim to fame is security, not simulation work). Astronomical periods have
costs, so you only want to pay for what is actually worth it, so it's certainly
a good thing that the MT has a k near its upper bound. PRNGs with shorter, but
still roomy periods like 2**128 are not worse because they have necessarily
"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