1
$\begingroup$

I am reading about Pseudo-Random Sequences in Applied Cryptography book by Bruce Schneier. Description is provided below.

A pseudo-random sequence is one that looks random. The sequence's period should be long enough so that finite sequence of reasonable length —that is, one that is actually used— is not periodic. If you need a billion random bits, don't choose a sequence generator that repeats after only sixteen thousand bits. These relatively short nonperiodic subsequences should be as indistinguishable as possible from random sequences. For example, they should have about the same number of ones and zeros, about half the runs (sequences of the same bit) should be of length one, one quarter of length two, one eights of length three, and so on. They should not be compressible. The distribution of run lengths for zeros and ones should be the same [643,863,99,1357].

My questions on above text

  1. What does statement "or example, they should have about the same number of ones and zeros, about half the runs(sequences of the same bit) should be of length one, one quarter of length two, one eights of length three, and so on. " mean?

  2. What does statement "Theere should not be compressible"?

  3. What is number 643,863,99,1357?

Thanks for your time and help

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

This is a about properties of a random sequence in general.

What does statement "or example, they should have about the same number of ones and zeros, about half the runs(sequences of the same bit) should be of length one, one quarter of length two, one eights of length three, and so on. " mean?

Consider a coin toss with a perfect coin (i.e. one that doesn't land on the side and lands on head or tail with 0.5 chance). Then about half of the time it will be a head or a tail. If you would toss it infinite times then you would have an equal amounts of heads and tails. However, if you toss it some other amount you'd expect about the same number of heads and tails.

If you would toss the coin an odd number of times you would certainly not have the same amount of ones and zeros, even with a perfect coin.

What does statement "Theere should not be compressible"?

Probably this should read "they should not be compressible". Things are compressible when a pattern can be found (think .zip files). If a pattern can be found then the sequence is not random. Note that small patterns can exist by chance, so this requirement is a rather heuristic (unless there is a different definition of compressible around).

Then again, you should not be able to always compress the random number sequences generated.

What is number 643,863,99,1357?

That looks like a set of references to me, nothing to do with the random numbers in itself :)

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks for explanation. other question I have is what does distribution of run lengths for zeros and ones should be same? in above paragraph $\endgroup$
    – venkysmarty
    May 10, 2017 at 9:05
  • 1
    $\begingroup$ One of the references is probably Golomb's work on max-length LFSR for the first sentences, and then some source about Kolmogorov complexity.@venkysmarty If you want additional information and have the book, then maybe check those references? That is exactly the reason for them being there. $\endgroup$
    – tylo
    May 10, 2017 at 9:19
  • 1
    $\begingroup$ Since compressibility in the sense of Shannon is a property of the source not the sequence it outputs, the only rigorous interpretation of incompressible is probably w.r.t. Kolmogorov complexity, which is defined for a single sequence. In fact only a fraction less than $2^{-k}$ of binary sequences of length $\leq n$ can have Kolmogorov complexity $< n-k$, see Cover & Thomas text on information theory, for a readable treatment. $\endgroup$
    – kodlu
    May 10, 2017 at 22:27
  • $\begingroup$ @kodlu The readable treatment would be required I guess :) If I'm not mistaken this doesn't invalidate my text, is my assumption correct? $\endgroup$
    – Maarten Bodewes ♦
    May 11, 2017 at 9:08
  • $\begingroup$ @MaartenBodewes, no of course it doesn't invalidate it. $\endgroup$
    – kodlu
    May 11, 2017 at 9:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.