Re: FFT test with few kbits

From: Ernst Lippe (ernstl-at-planet-dot-nl_at_ignore.this)
Date: 02/17/04 

Date: Tue, 17 Feb 2004 02:00:19 +0100

On Mon, 16 Feb 2004 19:52:07 +0000, Cristiano wrote:

> Ernst Lippe wrote:
>>
>> It would be much better to develop a single statistic that
>> uses all Fourier components, e.g. the largest absolute value.
>
> When you said that in another post, I tried some experiment, but I got
> nothing. Could you elaborate a bit?

There are good reasons to assume that each individual Fourier component
is normally distributed when N is large. The whole problem is
that we don't know the joint distribution of the Fourier components
because they are not independent.
Basically what I am trying to find is some value that can
be computed from the Fourier components for which we could
find the distribution, and for which we do not need the
assumption that the Fourier components are independent.
As an example I suggested using the largest value,
but unfortunately I cannot find its exact distribution.

>> I don't see any good reasons to discard the first Fourier component,
>> after appropriate scaling it has the same behaviour as the others.
>
> Please, could you show an example of "appropriate scaling"?
The values of the first Fourier component follow a binomial
distribution with p= 1/2, therefore the mean should be equal
to 1/2 N and the standard deviation should be equal to
1/2 sqrt(N).

>
>> It would be more symmetric to use the phase
>> and the absolute value of the complex value (although in a very
>> strict sense these are also not completely independent.
>
> As I said, the phase is always uniformly distributed, so I guess it can't
> show a thing.

Theoretically it could show problems in a RNG, but perhaps these
problems simply do not occur in the PRNG's that you have tested.
It seems possible that the phase is not a very useful test
for PRNG's.

> The absolute values are used by NIST, but the statistic they use is empiric
> and good only around 1e6 bits.

When you don't have an analytical solution, you must find
the distribution by simulation. Simulations for large values
of N are pretty expensive.

> I seen that the absolute values seem chi-square distributed but I'm not able
> to fit the distribution.

I would expect that the square of the absolute values would look
similar to the chi-square distribution. Actually, I can see
that the square of the real part (just like the square of the
imaginary part) should follow a chi-squared distribution, but
I am not completely certain that the square of the absolute value
(which is equal to the sum of the squares of the real and imaginary
part) also follows the chi-squared distribution because the
real and imaginary part are not independent.

Ernst Lippe

Relevant Pages

  • Re: FFT test with few kbits
    ... > uses all Fourier components, e.g. the largest absolute value. ... > after appropriate scaling it has the same behaviour as the others. ... to fit the distribution. ...
    (sci.crypt)
  • Re: Distribution of a transformed Gaussian variable.
    ... >I'm trying to find the distribution resulting from taking the square ... >root of the absolute value of a Normally distributed variable. ...
    (sci.stat.math)
  • Re: FFT test with few kbits
    ... >> is different from zero. ... In some cases we can only find the distribution by simulation ... > - I changed the normalization method using the expected standard deviation ... a single value from the whole set of Fourier components. ...
    (sci.crypt)
  • Re: FFT test with few kbits
    ... > There are good reasons to assume that each individual Fourier ... I think the central limit theorem holds. ... > that we don't know the joint distribution of the Fourier components ...
    (sci.crypt)
  • Re: FFT test with few kbits
    ... > There are good reasons to assume that each individual Fourier ... I think the central limit theorem holds. ... > that we don't know the joint distribution of the Fourier components ...
    (sci.crypt)
Quantcast