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 or (2) keep the transition function linear but
use a nonlinear output function
. 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
, and other more complicated transformations. Many
of them have output sequences that tend to behave much like i.i.d.
sequences even over their entire period length, in contrast
with ''good'' linear RNGs, whose point sets
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
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 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 ) 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]).