FFT test with few kbits

From: Cristiano (cristiano.pi_at_NSquipo.it)
Date: 01/29/04 

Date: Thu, 29 Jan 2004 10:21:25 GMT

Following the NIST's idea, I wrote a test using the FFT.
It seems very sensitive because a bad sequence is usually detected with few
kbits (even 1 or 2). This seems particularly useful to test the rng's (which
often are very slow).

My test uses the real part and the phase of the tranformed bits.
If the sequence is good, the real part follows a normal distribution with
|mean| = 0.5 and standard deviation = 0.3535158*sqrt(n); the phase follows a
uniform distribution from -PI to PI rad.

    How to test a sequence

1) generate a n-bit sequence (n should be at least 1000, I use 16 to 64
kbits for prng);
2) transform the sequence of 0's and 1's using the FFT;
3) discard the first value (which has always phase=0; now you have n/2-1
values);

        - real part:
4) calculate the mean and the standard deviation of the real part;
5) normalize the real part using (value - mean) / std_dev;
6) calculate the KS test with respect to a normal distribution;

        - phase:
7) normalize the phase using (phase + PI) / (2*PI) (you must get values from
0 to 1);
8) calculate the KS test with respect to a uniform distribution.

    Results

The p-values gotten from the KS test of the phase must be uniformly
distributed, so we just need to run the test M times and to do a 2nd level
KS test of the M p-values. We could say: if 0.01 < KStotal < 0.99 the
sequence pass the test.

The p-values gotten from the KS test of the real part are *not* uniformly
distributed. I checked my implementation of KS test with respect to a normal
distribution and it seems good, so I don't know how this happens.
In this case we could say: if there are more than 4% (2/50) of the p-values
< 0.01 the sequence is bad. In my experiments this seems good; an lcg, for
example, fails miserably the test.

Cristiano

Relevant Pages

  • Re: Most valuable poster
    ... flagellar evolution and speculate as to how an experimental programme ... always just one or two mutations away from what already existed? ... sequence space - regardless of their level of functional complexity. ... Ooh, the Poisson distribution! ...
    (talk.origins)
  • Re: Card Distribution in "Heirs to the Blood"
    ... that should happen from time to time as sequence>strings obviously ... This sort of sequential distribution (assuming it is a sequential ... If there are 54 different rares, there are 54 different places in the ...
    (rec.games.trading-cards.jyhad)
  • Re: Card Distribution in "Heirs to the Blood"
    ... that should happen from time to time as sequence>strings obviously ... This sort of sequential distribution (assuming it is a sequential ... If there are 54 different rares, there are 54 different places in the ...
    (rec.games.trading-cards.jyhad)
  • Re: Continuum hypothesis
    ... In the case of a uniform distribution over, the diestribution ... definitions of probability, real number and uniform, because they ... But the number of naturals goes to ... a sequence of partial sums to take the limit over. ...
    (sci.math)
  • Re: FFT test with few kbits
    ... "Cristiano" writes: ... ]2) transform the sequence of 0's and 1's using the FFT; ... that means that there is a bias in the distribution. ... ]6) normalize the imaginary part using imaginary_i / sd; ...
    (sci.crypt)