# Runs and Autocorrelation test

I have the book "Handbook of applied cryptography". In there we have example for random tests.

I have bits sequence [11100 01100 01000 10100 11101 11100 10010 01001]*4 length on this sequence n = 160. And I need test this sequence in order to understand this sequence is random or not. And problem with understanding this example.

Runs test I understand how they got

$$e_i=\frac{n-i+3}{2^i+2}$$

For $$k=1 \ \ e_1=\frac{160-1+3}{2^3} \ \ B_1 = 25 \ \ G_1 = 8$$

$$k=2 \ \ e_1=\frac{160-2+3}{2^4} \ \ B_2 = 4 \ \ G_2 = 20$$

$$k=3 \ \ e_1=\frac{160-3+3}{2^5} \ \ B_3 = 5 \ \ G_3 = 12$$

$$k=4 \ \ e_1=\frac{160-4+3}{2^6} \ \ \varnothing$$

And the question is how they got B and G?

Autocorrelation test.
In the book they write just (autocorrelation test) If d = 8, then A(8) = 100. The value of the statistic X5 is 3.8933. How they calculate this?

For the runs test example on page 182-183, partition the sequence into blocks and gaps without a block appearing next to a block and without a gap appearing next to a gap. Thus

111 000 11 000 1 000 1 0 1 00 111 0 1111 00 1 00 1 00 1 00 1111 000 11...

there are 81 groupings in total. Of these $$B_1=25$$ of them are 1, $$B_2=4$$ of them are 11, $$B_3=5$$ of them are 111, $$G_1=8$$ of them are 0, $$G_2=20$$ of them are 00 and $$G_3=12$$ of them are 000. There are also 7 instances of 1111 which we do not count.

In the autocorrelation test we look at equation (5.5) on page 182: $$X_5=2\frac{A(d)-\frac{n-d}2}{\sqrt{n-d}}$$ then with $$n=160$$, $$d=8$$ we have $$A(8)=100$$ and so $$X_5=2\times\frac{100-\frac{160-8}2}{\sqrt{160-8}}=3.89331.$$

The $$d=8$$ here is chosen arbitrarily for the example, $$A(8)$$ is calculated by lining up the first 152 terms of the sequence with the last 152. Thus

11100011000100010100111011110010010010011110001100... 00010001010011101111001001001001111000110001000100...

and counting where the entries are different. There are 100 out of 152 positions in total where this is the case.

• Thank you very much i got it! Commented Mar 3, 2023 at 13:30
• Sorry, but how you got the d and A(8)? Commented Mar 3, 2023 at 13:32