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

[Seth David Schoen]

Pierre Abbat writes:

> The last case is what I'm asking about, and with longer keys there may be 
> longer loops. I don't want to store the entire 8 GiB output of the Daphnes to 
> measure the period. I know how to measure the period of a sequence where each 
> number in the period occurs only once, but this is a sequence of bytes that 
> repeats with a period that may be in the millions. How can I measure the 
> period without storing the whole sequence?

I thought of the idea of taking a sample of, say, 10 or 20 bytes, and
then looking for where that particular sample recurs.  (A subsequence
of 10 bytes is very unlikely to recur by chance before the full period
if the overall data is random enough, although this is not the case
for less-random data.)

I asked an LLM for other possibilities, and it pointed out the whole
field of cycle detection algorithms such as Floyd's and Brent's
algorithms, which seem very suitable for your problem.

https://en.wikipedia.org/wiki/Cycle_detection

Wikipedia cites Knuth vol. 2, pp. 7-8, as giving Floyd's and
Brent's algorithms as exercises in the context of testing random
number generators for their periodicity (without having to store all
the output).  Sure enough, I looked this up and this is exactly how
Knuth suggests using them.  I'd heard of such a thing in the garbage
collection context (to figure out if a linked list contains a cycle),
but not for this kind of application.