How to prove these pseudo-random number generators don't repeat until running through the entire set?

Question

I just asked this question to find an algorithm for a pseudo-random number generator that generates 100% unique numbers for a bounded set of inputs. There are two answers I've seen. First is this one, which comes from here, and relies on quadratic residues:

b = (x, o) => x >= o ? x : (x <= o / 2) ? (x * x) % o : o - ((x * x) % o)

b32 = x => b(x, 4294967291)
b16 = x => b(x, 65519)
b8 = x => b(x, 251)

f32 = (x, o) => b32((b32(x) + o) ^ 1542469173)
f16 = (x, o) => b16((b16(x) + o) ^ 42703)
f8 = (x, o) => b8((b8(x) + o) ^ 101)

Second was an answer to the question, and relies on Linear congruential generators.

b = (m, a, c) => x => (a * x + c) % m
m = 2 ** 16
f32 = b(m, 97, (m >> 1) - 1)

The question I have is, how can you prove either the main idea in the first link, given by this image:

---

---

Or how can you prove that the linear congruential generator one, that either of them generate a complete set of unique numbers before repeating. That is, for $2^{32}$ values, it will loop through seemingly randomly to the lay observer, all of the $2^{32}$ values, without ever encountering the same number twice. Same goes for any bounded set of numbers.

Is there a proof for this? If so, what does it look like? If it's far too involved, then what is the gist of it? If there's no proof, well then why not? :) I tested it on some numbers in a bounded set and they were all unique, is that the only proof? Wondering because it would be cool to visualize how this is even possible, I can't imagine it currently.

Answer 1

I'll not prove them instead, I'll show you how to generate with a block cipher and will show a little proof that the output will be unique and visit all numbers from $0$ to $2^{32}-1$

A block cipher is a family of permutations. Formally;

$$E_K(P) := E(K,P): \{0,1\}^{k} \times \{0,1\}^n \rightarrow \{0,1\}^n$$ where the $k$ is the key size and $n$ is the block size. A key is expected to selects a random permutation from all possible premutations from $\{0,1\}^n \rightarrow \{0,1\}^n$, that is there are $(2^n)!$ permutations that we select only $2^k$ of them, enough theory.

There is a block cipher called Skip32 that has a 32-bit block size and 80-bit key, though not secure. Now how to generate all number;

1. Select a uniform random, key $k$
2. Set a 32 bit counter $counter=0$
3. output $r = E(k,counter)$
4. if $counter = 2^{32}-1$ then exit
5. $counter++$
6. return step 3.

Since a block cipher is a permutation, it will output unique values for each input, remember, we need the reverse for the decryption. Counter visits all possible values between $0$ and $2^{32}-1$ then the output will be a random order of these values.

On the bonus side, you have $2^{80}$ different ( expected) random number generator for each of the keys.

If you want the numbers between $1$ to $2^{32}$ than just increment the output.

If you don't want the 0 but in the range $1$ to $2^{32}-1$ then a maximal LFSR with length 32 can be a solution, too.

The bonus, the cipher has javaScript implementation, too. And you can turn into a random number generator, very esaily.