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.