the alternative explanation is of course that the diehard cdrom data,
http://stat.fsu.edu/pub/diehard/cdrom/ is not "true" random data.

- FFT test in anything less than 1e6 sample sizes

a test on the minimum recommended length of 1000 or a
anything up to around 1,000,000 bits, shows non-uniform
distribution of p-values on what is purported to be
"true" random data.

on a test of length 1,000, the C8 histogram bucket,
representing p-values of between 0.7 and 0.8, was empty!

- Rank test on anything less than 1e6 sample sizes

a test of 100,000 sample sizes on 8,000 runs gives a
skewed histogram of p-values - sufficient for the data
to be determinined as non-random.

- Lempel-Ziv test on anything.

this one is particularly weird: on sample sizes of 1e6,
you should not be looking for a uniform distribution of
p-values but instead should be looking for a small percentage
of extra p-values in the C4 (0.3 - 0.4) histogram bucket!

in short, stay well clear of using this test.

many people, including myself, will be using the csrc's
statistical test suite, sts, which is available from the above URL.

i have been using this program for long enough now to have
become suspicious of some of its foibles and quirks.

eventually i downloaded the diehard cdrom data this is purported
to be a "true" random source, as a baseline comparison.

if anyone is using the sts test suite, please be suspicious of the
following tests, and avoid them. the list of tests which i am
suspicious of is incomplete: there could be others, but they could
equally well be perfectly okay.

i strongly urge anyone performing statistical analysis of their PRNGs
and encryption algorithms to DOUBLE CHECK the statistical test suite
tools that they are using against a known "true" random baseline.

the alternative explanation is of course that the diehard cdrom data,
http://stat.fsu.edu/pub/diehard/cdrom/ is not "true" random data.

- FFT test in anything less than 1e6 sample sizes

a test on the minimum recommended length of 1000 or a
anything up to around 1,000,000 bits, shows non-uniform
distribution of p-values on what is purported to be
"true" random data.

on a test of length 1,000, the C8 histogram bucket,
representing p-values of between 0.7 and 0.8, was empty!

- Rank test on anything less than 1e6 sample sizes

a test of 100,000 sample sizes on 8,000 runs gives a
skewed histogram of p-values - sufficient for the data
to be determinined as non-random.

- Lempel-Ziv test on anything.

this one is particularly weird: on sample sizes of 1e6,
you should not be looking for a uniform distribution of
p-values but instead should be looking for a small percentage
of extra p-values in the C4 (0.3 - 0.4) histogram bucket!

the exact reason why this test gives a non-uniform distribution
of p-values isn't clear, but modifying src/results.c HIST_SIZE
from 10 to 100 gives some clues as to what is going on.

in short, stay well clear of using this test.

ehbedehbethat's'all'folks.

l.
The tests give passes but the distribution of the p values are

eventually i downloaded the diehard cdrom data this is purported
to be a "true" random source, as a baseline comparison.

Luke Kenneth Casson Leighton wrote:
the alternative explanation is of course that the diehard cdrom data,
http://stat.fsu.edu/pub/diehard/cdrom/ is not "true" random data.

Or that your implementation is bad.

- FFT test in anything less than 1e6 sample sizes

a test on the minimum recommended length of 1000 or a
anything up to around 1,000,000 bits, shows non-uniform
distribution of p-values on what is purported to be
"true" random data.

on a test of length 1,000, the C8 histogram bucket,
representing p-values of between 0.7 and 0.8, was empty!

Really!? I suggest to double check your implementation!

Running that test 100 times I get a very good distribution; all the bins
have about 10 p-values.

- Rank test on anything less than 1e6 sample sizes

a test of 100,000 sample sizes on 8,000 runs gives a
skewed histogram of p-values - sufficient for the data
to be determinined as non-random.

Also in this case I get the p-values: perfectly skewed (-0,031), correctly
binned and evenly distributed.

- Lempel-Ziv test on anything.

this one is particularly weird: on sample sizes of 1e6,
you should not be looking for a uniform distribution of
p-values but instead should be looking for a small percentage
of extra p-values in the C4 (0.3 - 0.4) histogram bucket!

I don't know what kind of code you are using.

You should get p-values from 0
to 0.5 because they said "The test is preferably one-sided" so they use 1/2
erfc(...). But we need a p-values from 0 to 1, so you must throw away 1/2.

This way I get a good distribution (with good generators).

in short, stay well clear of using this test.

In short: you have not read the NIST paper,

you have not checked your
implementation against the test vectors and you don't know what you're
saying, so you should avoid this kind of claims.

On 16 Jan 2004 05:22:14 -0800, lkcl@lkcl.net (Luke Kenneth Casson
Leighton) wrote:

[snip happens]

eventually i downloaded the diehard cdrom data this is purported
to be a "true" random source, as a baseline comparison.


DANGER WILL ROBINSON!

There is a known problem with early versions of the "random numbers"
on some diehard CDs. Newlines (0x0a) were appended to the
Carriage Returns (0x0d). (You can thank Microsoft for that...)
Check the data you have and see if there are any CRs
followed by something other NL.

On 16 Jan 2004 05:22:14 -0800, lkcl@lkcl.net (Luke Kenneth Casson
Leighton) wrote:

The tests give passes but the distribution of the p values are
skewed. There appears to be a problem with the way the
p values are calculated beyond the tails.

perhaps with cooperation we may both understand what is going on, and
thereby
improve the quality of the tests.

the people at csrc.nist.gov inform me that they used blum-blum-shub
as the "baseline" for the lempel-ziv test (i haven't asked them about
the other tests) and that they then took EMPIRICALLY OBSERVED values
for the mean and standard deviation of the information that generates
the p-values.

if they did the same on one or two other tests, it's possible that
they either didn't take a large enough pseudo-random sample from
which to derive the empirical mean and s.d., or that there is a
problem with the pseudo-random generator that they used.

either way, a skew of the p-values is, as you say, introduced.

no "implementations" are involved.

Luke Kenneth Casson Leighton wrote:

the people at csrc.nist.gov inform me that they used blum-blum-shub
as the "baseline" for the lempel-ziv test (i haven't asked them about
the other tests) and that they then took EMPIRICALLY OBSERVED values
for the mean and standard deviation of the information that generates
the p-values.

They have also used sha-1 based generator to get the mean and the variance.
They updated those values with:
mean = 69588.20190000
variance = 73.23726011
which are good enough.

Luke Kenneth Casson Leighton wrote:
no "implementations" are involved.

Obviously they must have meant implementation of the tests.

"Cristiano" <cristiano.pi@NSquipo.it> wrote in message news:<a%dOb.134287$_P.4856973@news4.tin.it>...
Luke Kenneth Casson Leighton wrote:

the people at csrc.nist.gov inform me that they used blum-blum-shub
as the "baseline" for the lempel-ziv test (i haven't asked them about
the other tests) and that they then took EMPIRICALLY OBSERVED values
for the mean and standard deviation of the information that generates
the p-values.

They have also used sha-1 based generator to get the mean and the variance.
They updated those values with:
mean = 69588.20190000
variance = 73.23726011
which are good enough.

try one of the two following things, which i will repeat for a second time:

1) increasing HIST_SIZE in src/results.c from 10 to 100: you will note
that the p-values fall into specific buckets and are NOT uniformly
distributed.

if that's not obvious enough, increase the HIST_SIZE to 1,000.


2) run at least 4,000 runs of 1e6 samples.

could someone else help by running a test and send [me/newsgroup] the
results?

i get histograms like this on 800 runs of 1e6 sample-length, using
the diehard cdrom data from november.

c1 c2 c3 c4 c5 c6 c7 c8 c9 c10 p-value
80 90 95 117 65 70 93 85 79 78 0.00011

the 117 is _very_ close to being unacceptable: running a 200mb or
500 mbyte test, the skew is the same and the p-value test of the
histogram comes out at 0.00000 - i.e. failure [non-uniform].

l.

Luke Kenneth Casson Leighton wrote:

the people at csrc.nist.gov inform me that they used blum-blum-shub
as the "baseline" for the lempel-ziv test (i haven't asked them about
the other tests) and that they then took EMPIRICALLY OBSERVED values
for the mean and standard deviation of the information that generates
the p-values.

They have also used sha-1 based generator to get the mean and the variance.
They updated those values with:
mean = 69588.20190000
variance = 73.23726011
which are good enough.

if they did the same on one or two other tests, it's possible that
they either didn't take a large enough pseudo-random sample from
which to derive the empirical mean and s.d., or that there is a
problem with the pseudo-random generator that they used.

either way, a skew of the p-values is, as you say, introduced.

No skewed p-values introduced.

Are you able to calculate the mean and the variance by yourself without
whimper?
I done that for n = 10e6 bit and I use this sample size instead of 1e6.

Cristiano

Leslie 'Mack' McBride