Hugo Mills wrote:
> On Wed, May 14, 2008 at 11:02:58PM +0000, Nick Chalk wrote:
>> Chris Oattes <mailinglist@???> wrote:
>>> Assume you have a stream of numbers in base 10
>>> (i.e. made up of a series of digits from 0-9).
>>>
>>> This stream of numbers would be considered
>>> random if, given the first x digits, it is
>>> impossible to determine the x+1 th digit with
>>> probability > 1/10. That is to say, each digit
>>> is equally likely to be any one of the possible
>>> values.
>> I'm no cryptanalyst - or mathematician - so I'll
>> try to dig up an archive of the discussion.
>
> Could be interesting (or scary, or both).
>
>> I have a vague recollection that part of argument
>> was about sequence repetition. For cryptography,
>> it's not just a case of whether you can predict
>> the next digit, but whether earlier parts of the
>> 'random' sequence allow you to infer properties of
>> future parts of the sequence.
>
> That's covered by Chris's definition: given the first x (decimal)
> digits, can you predict the x+1th digit with probability greater than
> 0.1?
>
> Hugo.
>
>
From my non-cryptanalyst's point of view I would hazard a guess that a
good first stab at a randomness test would be to try every data
compression tool available to see if your 'random' data compresses.
This still leaves problems for data such as Pi, a series of consecutive
prime numbers, and encrypted data, which I'm guessing don't compress
very well.
It seems to me that this is the same problem as deciphering SETI, should
a complex extraterrestrial signal ever be received - how to distinguish
a pattern in the seemingly random data. So if you can solve one you
probably have found the solution to the other. At which point you would
probably have developed a universal decryption algorithm too.
I suspect it's a very hard mathematical problem ;-)
Simon C.
