Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

To test a 'random' bit sequence for cryptographic strength I have been using the NIST's Non-overlapping Template Matching Test (See page 2-14 but I will explain here). This test uses a non-periodic bit template $B$ of length $m$ and counts the occurrences of the template in the bit sequence over $N$ blocks (where the blocks are just the original bit sequence split up into chunks). Then a Chi-squared test is done.

Let's say $B$ is $0001$, which is non-periodic.

If the bit sequence is $000010100010000...$ then we have...

    0001                  no match
     0001                 match. advance by m
         0001             no match
          0001            no match
           0001           match. advance by m...
               0001       no match.

Now the question is why should we particularly care about the distribution of non-periodic patterns as compared with periodic ones? Are they special in some way as related to random number generators?

share|cite|improve this question

I contacted someone from the NIST to answer this question: essentially the counting of aperiodic templates is different to the counting of periodic ones, and the maths is easier when considering aperiodic ones. Unfortunately my training is not good enough to give a better explanation, however there is more information in Volkovich and Rukhin, the Journal of Statistical Computation and Simulation, v 78, 2008, 1131-42, which well beyond my mortal soul.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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