2 ms·
> We know that a PRNG with N bits of state must necessarily repeat after 2^N invocations, but it requires further proof that a given PRNG will not repeat at sma
by dragontamer 5y ago
> We know that a PRNG with N bits of state must necessarily repeat after 2^N invocations, but it requires further proof that a given PRNG will not repeat at smaller intervals.
Yes, that's somewhat important for "smaller" 64-bit or 128-bit states.
But at 512-bit states, the "average loop" is 2^256 (birthday paradox), so no one really cares at that point. We can see that Mersenne Twister is overprovisioned: 19937 bits of state and all 2^19937 visited in some order.
But in practice, 64-bits worth of cycles (18-quintrillion) is sufficient for single-threaded simulations, and 128-bits is sufficient for multithreaded simulations.
> In light of the above, is it possible to prove this (through some property of AES)?
Yeah. AES is a block cipher that maps 128 bit blocks into "encrypted" 128-bit blocks. The reverse-AES (I'll call it unAES in this post) provides us the 1-to-1 unmapping as well.
Meaning unAES(AES(0, key), key) == 0. unAES(AES(1, key), key) == 1. unAES(AES(2, key), key) == 2. (Etc. etc. for all possible 2^128 blocks)
By the pidgeon-hole principle, we have 2^128 blocks associated with AES-encrypted blocks (named AES(0, key), AES(1, key)... AES(2^128-1, key)), and 2^128 blocks associated with our plaintexts (0, 1, 2, 3... 2^128-1). The only way all 2^128 map to each other is through a 1-to-1 bijection.
Or in another way: AES(X, key) == AES(Y, key) if-and-only-if X == Y. This is because deAES(AES(X, key), key) == deAES(AES(Y, key), key) if-and-only if X == Y.
Done. We know the AES-crypto method therefore only "loops" after 2^128, exploring the entire state-space. 2^128 possible inputs, 2^128 possible outputs, pigeonhole principle. QED, done.