2.5 Nonlinear RNGs

All RNGs discussed so far are based on linear recurrences and their structure may be deemed too regular. There are at least two ways of getting rid of this regular linear structure: (1) use a nonlinear transition function $f$ or (2) keep the transition function linear but use a nonlinear output function $g$. Several types of nonlinear RNGs have been proposed over the years; see, e.g., [2], [17,18,26,31], [36,82], and [88]. Their nonlinear mappings are defined in various ways by multiplicative inversion in a finite field, quadratic and cubic functions in the finite ring of integers modulo $m$, and other more complicated transformations. Many of them have output sequences that tend to behave much like i.i.d. $U(0,1)$ sequences even over their entire period length, in contrast with ''good'' linear RNGs, whose point sets $\Psi_t$ are much more regular than typical random points ([18,51,50,82]). On the other hand, their statistical properties have been analyzed only empirically or via asymptotic theoretical results. For specific nonlinear RNGs, the uniformity of the point sets $\Psi_t$ is very difficult to measure theoretically. Moreover, the nonlinear RNGs are generally significantly slower than the linear ones. The RNGs recommended for cryptology are all nonlinear.

An interesting idea for adding nonlinearity without incurring an excessive speed penalty is to combine a small nonlinear generator with a fast long-period linear one ([1,50]). [50] show how to do this while ensuring theoretically the good uniformity properties of $\Psi_t$ for the combined generator. A very fast implementation can be achieved by using precomputed tables for the nonlinear component. Empirical studies suggest that mixed linear-nonlinear combined generators are more robust than the linear ones with respect to statistical tests, because of their less regular structure.

Several authors have proposed various ways of combining RNGs to produce streams of random numbers with less regularity and better ''randomness'' properties; see, e.g., [7], [31,23,34,36], [21,71], and other references given there. This includes shuffling the output sequence of one generator using another one (or the same one), alternating between several streams, or just adding them in different ways. Most of these techniques are heuristics. They usually improve the uniformity (empirically), but they can also make it worse. For random variables in the mathematical sense, certain types of combinations (e.g., addition modulo $1$) can provably improve the uniformity, and some authors have used this fact to argue that combined RNGs are provably better than their components alone ([4,13,71,23]), but this argument is faulty because the output sequences of RNGs are deterministic, not sequences of independent random variables. To assess the quality of a combined generator, one must analyze the mathematical structure of the combined generator itself rather than the structure of its components ([38,37,40,50,88]).