[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: more IPG and random numbers



At 09:24 PM 12/3/96 -0800, Eric Murray wrote:
>I did some more experiments with the IPG stream-cipher
>algorithim and random number tests.  Since IPG claim that their
>algorithim passes chi-square tests of randomness, I found
>a chi-square test program.  It's written by Peter Boucher
>and was posted to sci.crypt in '93 (<[email protected]>).

Eric,

The chi-square test is fairly easy to implement.  Understanding the
alogrithm and interpreting what the test results mean is as important as a
proper implementation.  An excellent text that covers testing PRNGs
(including, chi-square, KS, runs (up, down, above & below the mean), and
autocorrelation) is Simulation Modeling & Analysis, by Law & Kelton.

>> Does the 'runs up' (or 'runs down') test with run-length equal to two
>> get me anything over the standard chi-square test?  I left it in.

Yes.  It tests yet another aspect of "is the data truly random?"

>First I ran the output from my version of the IPG algorithim that I
>posted a couple days ago :
>
>% ./boucher < ipg.out
>Occurances:  n =  12000000, V=-8375833.71
>Character occurances non-random
>Successions: n =     46875, V=62287.82
>Character successions non-random

Unless the V is a typo, there is an error in the code.  The chi-square
statistic can never be negative.

>Then I ran output from a test RNG that's basically a loop around random():
>
>% ./boucher < myrandom/out
>Occurances:  n =   3414720, V=213050.62
>Character occurances non-random
>Successions: n =     13338, V=1143.41
>Character successions non-random

I did considerable testing on random() a while back.  It is actually quite
good at producing a uniform distribution.  There were other problems however
(notably autocorrelation in triplets).

>Eric Murray  [email protected]  [email protected]  http://www.lne.com/ericm
>PGP keyid:E03F65E5 fingerprint:50 B0 A2 4C 7D 86 FC 03  92 E8 AC E6 7E 27 29 AF

I suggest you take a look at the chi-square program and check it for errors.
Based on the above observations, I am a little suspicious of your results. 

As a side note, I tend to test PRNGs using stream lengths that are similar
to what I will need in a real use of the generator.  I also test multiple
seeds, because statistically, some seeds will fail.  Of course, testing
multiple seeds has its own problems (see the bonferroni inequality) of which
most non-statisticians are unaware.  

I have been curious for a while about developing a statistical test that
would examine the expected number of failures of a repeated statistical
test. Haven't had the time to look into it yet though - not enough hours in
the day.
*******************************************************
Clay Olbon			    [email protected]
engineer, programmer, statistitian, etc.
**********************************************tanstaafl