[Hardware] Notes... The case for an open client

Elektron elektron_rc5 at yahoo.ca
Tue Aug 17 00:29:37 EDT 2004


>> Which for 453 or so bits, is biased, but not horribly so.
>
> The next question a statistician will ask himself is wether this  
> observed bias is statistically significant. Generally the result is  
> significant if there is less than a 5% chance that the result was due  
> to random fluctuations.
>
> You don't need to be a math head to compute the significance. Just  
> generate a large number of random samples just like the set above and  
> count the number that have the same or greater bias.

I wouldn't sum the run lengths, since all the keys are of different  
lengths. Although it's not entirely correct, for simplicity's sake, we  
can string all the keys together:
0x67b9e0ec4f20d95e43d26dd827510678042628da989a5ab31114f918c79c9f1be5823d 
986e6bf1be4bda9909C24C742B5339D0F454C17DDE63

Binary,
0b1100111101110011110000011101100010011110010000011011001010111100100001 
111010010011011011101100000100111010100010000011001111000000001000010011 
000101000110110101001100010011010010110101011001100010001000101001111100 
100011000110001111001110010011111000110111110010110000010001111011001100 
001101110011010111111000110111110010010111101101010011001000010011100001 
001001100011101000010101101010011001110011101000011110100010101001100000 
1011111011101111001100011

232/456 bits are ones. That's a little on the high side, but only by  
37%.

As for run lengths, we can split it up into words (14.25 of them) and  
look at max run lengths (you can look at all of them, but then you have  
trouble measuring the bias). This is probably too small a sample to  
draw any conclusions, though.

There's also a small problem with measuring the bias of run lengths,  
but for simplicity's sake, if we have 456/(2^32*32) (approx. 3.318e-9)  
of the bits in the study, then we should have the same proportion of  
each run length (pretending they're all 32-bit, which they aren't, but  
anyway). E.g. with 35433480192 length-1 runs, in 456 bits, we should  
have 35433480192*3.318e-9 = 117.6. Continuing this,

   1     2     3     4     5    6    7    8    9
------------------------------------------------
117.6  57.0  27.6  13.4   6.5  3.1  1.5  0.7  0.3    Predicted runs
  97    67    27    18    11    1    0    1    0      Actual runs

Then we have the problem of deciding just how unlikely this is (and  
then, though there are more 5-bit runs than usual, there are also more  
2-bit runs than usual).

- Purr



More information about the Hardware mailing list