[Cryptography] How do I tell if a byte sequence repeats?

[John Denker]

Please allow me to answer a slightly different question, namely
how to test a sequence for grossly non-random behavior more
generally (rather than a repeating cycle specifically).

Look at the snippet of length M=10 bytes starting at position
zero, and then starting at position 1, and so on. If the main
sequence has length 2³², then there are just shy of 2³² such
snippets.

Store all the snippets in a /trie/. Since there are 2⁸⁰ possible
snippets, of which 2³² actually occur, the observed snippets are
verrry sparse in the space of all possible snippets. So if you
observe a collision, it is evidence of grossly nonrandom behavior.

You can dress up the trie to record the position (within the main
sequence) where each snippet occurred. So when you see an N-way
collision, you know where each of the N members occurred.

A cycle will produce abundant collisions, but there are also many
many other ways for collisions to occur.

This is memory-intensive, but not insanely so by today's standards.

With minimal additional work, the same calculation can report
on collisions of length m for all m less than or equal to M.