1
$\begingroup$

What is the best way to detect repeating sequences of random numbers?

For example, say I got two random number generators (RNG). One of them has been tampered with and is repeating the sequence of random numbers after every N iterations. The other RNG has not been tampered with and is producing random numbers like it should.

However, one of them is repeating its output every N bytes. N can be small or very large. How to detect this in a reliable and economic way?

Is using rolling hashes (like rsync does) a viable approach?

$\endgroup$
1

1 Answer 1

1
$\begingroup$

does not yet seem to be a duplicate on this very site:
cycle detection, see also where hares catch up with turtles
(would-be comment: the question first states repetition every N iterations, next every N bytes.)
(If it didn't carry over: for each PRNG to check, have a clone. For each change in state of the original one, trigger two in the clone. If the states get identical, you detected a cycle. No deterministic PRNG with limited state can avoid it. The states need not be as small as the results; they rarely are, nowadays, and the cycle lengths are huge.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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