Frequency Test (Menu Analysis \ Analyse Randomness)

Choosing this menu entry opens the dialog Frequency Test.

This test tests the uniform distribution of the values generated by a pseudorandom number generator. An attempt is made to identify any deviations from a unidimensional uniform distribution. This entails checking the number of zeros and ones in sequence s against the expectation that if the sequences were genuinely random, one would expect the numbers of zeros and ones to be virtually the same. In the literature this test is also referred to as the Monobit Test. Let n0 and n1 be the number of zeros or ones in s. The test statistics used are given by

X1 = (( n0 - n1 ) ^ 2) / 2

where X1 follows a chi^2 distribution with one degree of freedom, provided that n >= 10. For practical purposes, a length of n> 10,000 is recommended. If n0 = n1, then X1 = 0; the bigger the value of X1 the greater the discrepancy between the observed and expected frequencies of zeros and ones.

The table for the chi^2 distribution gives the value 3.8415 for the 0.05 significance level with one degree of freedom. Thus, if X1 = 3.8415, then the tested sequence passes the test, otherwise it fails in the test. If the value of X1 obtained for a given sequence is 0, one might decide to reject the sequence on the grounds that a perfect score actually looks suspicious!

It is not sufficient to apply the frequency test only once to a sub string of the generator since, for example, at a significance level of 0.05 in 5 out of 100 cases a "good" generator would be wrongly rejected. Therefore the test should be applied several times to different sub-sequences and then the distribution of the test statistics obtained should be checked using the chi^2 test.

In the frequency test dialog it is possible to determine significance level, offset and test length.

Example of a Frequency Test

By way of illustration, a classical frequency 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.

The numbers of zeros and ones in s are n0 = 74 and n1 = 86 respectively. The frequency test produces a test statistic of

X1 = ( 74 – 86 ) ^ 2 / 160 = 0.9

With a chi^2 distribution with one degree of freedom and a significance level of alpha = 0.05, the critical range for X1 lies above 3.814.

With X1 = 0.9 <= 3.814, sequence s passes the frequency test.

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