Pseudorandom number generator

Remarks

Example: $S = \set{0, \ldots, 7}$, $T(s) = (5s + 1) \bmod 8$, $U = [0, 1)$, $G(s) = s/8$ and $s_0 = 0$; all five clauses hold, and the outputs are $0, 0.125, 0.75, 0.875, 0.5, 0.625, 0.25, 0.375$, then repeat. Non-example: the sequence of decimal digits of $\pi$ is not eventually periodic, because $\pi$ is irrational. It is not the output sequence of any such tuple, since a finite state space as in clause 1 forces the outputs to be eventually periodic. Since $S$ is finite, the sequence $(s_i)$ is eventually periodic, with period at most $\abs{S}$; if $T$ is a bijection it is purely periodic. The definition is purely structural; the quality of a generator is judged by its period, by the uniformity of tuples $(u_i, \ldots, u_{i+k-1})$, and by statistical tests. Generators for cryptography must in addition be unpredictable from past outputs, which is a stronger requirement.