The first test I wrote may be a minor improvement on the simple test, as it merely ensures that the value returned by the rng is not always the same. (it is plausible that an rng might return the same data twice).<br><br>For the second test I chose a large sample so that the average of all the data would be roughly 128, I chose the large variation sort of out of the air, although the average of a large sample should (statistically speaking) be very close to 128. After running about 10 tests the values were never outside of 128 +/- 2.<br>
<br>I might try plotting a graph of (x,y) byte pairs and try calculating correlation co-efficients.<br><br><div class="gmail_quote">2008/11/8 Sergey Chernov <span dir="ltr"><<a href="mailto:sergey.chernov@thrift.ru" target="_blank">sergey.chernov@thrift.ru</a>></span><br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
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.<br>
<br>
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 :)<br>
<br>
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.<br>
<br>
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).<br>
<br>
For sure there must be a plenty of better tests by now, but I'm not familiar with them.<br>
<br>
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 :)<br>
<br>
Sergey Chernov<br>
<a href="mailto:sergey.chernov@thrift.ru" target="_blank">sergey.chernov@thrift.ru</a><br>
<br>
<br>
<br>
08.11.2008, Χ 1:12, Dwayne C. Litzenberger ΞΑΠΙΣΑΜ(Α):<div><div></div><div><br>
<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
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.<br>
<br>
(* Someone please correct me if I'm wrong, since I'm still not very good at reasoning with probability.)<br>
</blockquote>
<br>
</div></div><br>_______________________________________________<br>
pycrypto mailing list<br>
<a href="mailto:pycrypto@lists.dlitz.net" target="_blank">pycrypto@lists.dlitz.net</a><br>
<a href="http://lists.dlitz.net/cgi-bin/mailman/listinfo/pycrypto" target="_blank">http://lists.dlitz.net/cgi-bin/mailman/listinfo/pycrypto</a><br>
<br></blockquote></div><br><br clear="all"><br>-- <br>Sam Phippen<br><br>Please avoid sending me Word or PowerPoint attachments.<br>See <a href="http://www.gnu.org/philosophy/no-word-attachments.html" target="_blank">http://www.gnu.org/philosophy/no-word-attachments.html</a><br>