[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