where

The linear congruential method has the advantage of being very fast,
requiring only a few operations per call. It has the disadvantage that
it is not free of sequential correlation on successive calls. Thus for
SIMON we are using a random generator that
shuffles
the output of a
linear congruential method to remove the least significant bit correlations
[96]. To achieve the shuffling, a computed random number *r*_{n} is not
output as the *n*-th random number, but rather at a randomized later
call.

Another derivative of a linear congruential method is a
nonlinear
congruential method, of which the inversive congruential method is a special
case.

The
inversive
congruential method has superior statistical properties
compared to the plain linear congruential method [91]. On the
other hand the
calculation of
for a given *x*_{n} consumes additional
computational resources and thus this method is not so efficient. The
Euclidean algorithm to calculate
for a given *x*_{n} from
[62] terminates in average after
steps.

The
shift-register generators
received their name from the fact, that such
generators can be built in hardware from shift registers with a
feedback. If *m* is a small prime, usually *m*=2, a shift-register
method can be written as

with
and integers
.
In the case of *m*=2shift-register generators can be implemented efficiently since only binary
arithmetic is needed. They too have better statistical properties than a
simple linear congruential method.

A complicated computation of random numbers does not necessarily
guarantee their randomness. In the contrary the more complicate the harder
it is to derive theoretical justifications for the soundness of the method.
However, the only way to guarantee the quality of a random generator is
thorough testing. One test for the accuracy of the probability distribution
of the PRN is to plot their probability function

where *p*(*r*) is the probability distribution of the PRN. The function *F*(*x*)
gives
the probability that the random number *r* is smaller than *x*.
Fig. 4.6 compares *F*(*x*) for *x*<10^{-4} for the
above explained random generator that SIMON uses and a simple linear
congruential method with the parameters
(*m*,*a*,*c*)=(714025,1366,150889).

The simple linear congruential method shows deviations to the ideal characteristic

In comparison the right side shows points for the shuffled congruential method used in SIMON. There such parallel hyperplanes are not visible.