[pycrypto] Test code - Random

[Sergey Chernov]

I'm sorry if I'm telling something stupid, since I was not working  
with RNGs analysis for about 18 years, but from what I still remember.  
There was a test (in fact, series of tests) that surprisingly failed  
lot of these old times RNGs. It's sort of N-dimensial bins histogram.

The simplest was easy. Let's talk pairs of N-bit randoms as (x,y)  
coordinates in a finite rectangle (using N or mod) and see whether  
they would tend to cluster. I've seen in my own eyes that one RNG that  
was supposed to be sufficient, was constantly generating a few small  
triangles leaving the rest clear :)

So, the general test we were performed was kind of following. Let's  
take N-dimensional cube and fill it with RNG series of size L, then  
check how even it fills the cube. Simplest case is to divide it to  
equal clusters (bins), so there should be, say, L/1000 clusters least,  
calculate how many pseudo-random points hit each bin and see how plain  
is this histogram. It should not vary too much if the RNG is ok and L  
is big. We can, say, check the standard deviation. Better to check  
several bins size, using various random primes as factors for bins  
sizes. Then increment N and check it again.

I've read in late 80s that such test failed on some very famous RDBMS  
system of these old good times (as I remember, all dots filed 64 plans  
in the 3(?)D cube or so).

For sure there must be a plenty of better tests by now, but I'm not  
familiar with them.

The probability you mentioned should be, as for me, 1e-256. One famous  
mathematician, namely Kolmogorov, once said, that there is no such  
things as 1e-100 probability, there is only the impossibility :)

Sergey Chernov
sergey.chernov at thrift.ru



08.11.2008, в 1:12, Dwayne C. Litzenberger написал(а):

> I'm not sure what your proposed TestNotAlwaysEqual test offers that  
> SimpleTest does.  Presumably the purpose of this new test is to  
> avoid the case where a correctly-functioning RNG returns two  
> identical 128-bit numbers in a row.  While that may be possible, I'm  
> really not concerned about it, since according to my calculations*,  
> the probability that SimpleTest fails is 2**-128.   
> TestNotAlwaysEqual adds another test that can  fail in the same way,  
> but with a probability of 2**-1280.  I don't see why that would be  
> necessary.
>
> (* Someone please correct me if I'm wrong, since I'm still not very  
> good at reasoning with probability.)

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 2193 bytes
Desc: not available
Url : http://lists.dlitz.net/pipermail/pycrypto/attachments/20081108/35822f32/attachment-0001.bin