Autocorrelation Test (Menu Analysis \ Analyse Randomness)

The purpose of this empirical test of independence is to check correlations between succeeding outcomes of the pseudorandom number generator and/or between the binary sequence s and an alternative version of s that is displaced by t positions.

Let t be a number, 1 <= t <= (n / 2) and fixed. The number of bit positions in s which do not agree with the version of s that has been displaced by t positions is determined by

D(t) = sum[i = 0; i = n – t – 1] si XOR s(i + t)

The test statistics used are given by

X5 = 2 * [(D(t) – [(n – t) / 2]) / (n – t) ^ (1 / 2)]

whereby X5 approximates an N(0, 1) distribution, provided that n - t >= 10. As both small and large values for D(t) are unexpected, a two-tailed test is recommended.

Example of an Autocorrelation Test

By way of illustration, a classical autocorrelation test will be carried out on the short binary sequence

s =
00010111 01101101 01111101 11110011 00101111
00001111 10100100 11001111 11000011 11010001
11010001 00101110 11010100 11000011 01010001
11010110 00110010 10001111 00000111 01000111

of length n = 160 (20 bytes). The significance level is set with alpha = 0.05.

We choose t = 8. The sequence s departs from the copy of s displaced by 8 positions precisely at D(8) = 68 positions. The autocorrelation test thus produces a test statistic of

X5 = 2 * (68 – [(160 – 8) / 2) / (160 – 8) ^ (1 / 2) = -1.29777

The limit for a normally distributed test statistic X5 is 1.6449 at a significance level of alpha = 0.05. With X5 = -1.29777 <= 1.6449, sequence s passes the autocorrelation test.

Reference: Christian Schiestl, Pseudozufallszahlen in der Kryptographie, in Klagenfurt, 1999.