A random-walk pseudorandom byte generator (Q1591115)

Sometimes it is necessary (e.g. in the case whe we must use a very cheap hardware) to design a random number generator based on an algorithm that must not use any multiplication and must use a very short (8 bits or 16 bits) arithmetics. The problem can be solved if we use a generalization of random shuffling. One of the oldest solution for a quite short shuffling table and the 16 bit arithmetics was published by \textit{J. Kral} [Inf. Process. Lett. 1, No. 4, 164-167 (1972; Zbl 0236.65007)]. The authors present a new solution of this problem. Their new generator uses 8 bit arithmetics, addition only, and a table \(T\) containing 256 randomly chosen different vectors of the length 256. Each vector is a permutation of all different 256 bytes (i.e. \(T\) is a 64kB table). The table \(T\) is constant. The generator further uses a vector \(D\) of 256 randomly initialized bytes. The algorithm uses a hidden random generator \(G\) implemented via operations on \(D\) (a similar generator was studied in the paper metioned above). The outputs of \(G\) are inputs of a random walk over \(T\). The generator was excessively tested using 18 different tests repeated many times. The outputs of the tests were used in metatests (one of the oldest uses of metatest is in the above metioned paper). The metatest tests the uniformity of the statistics \(P(x\geq a)\) where a is the value of the statistics generated by the test and \(P\) the probability. A proof of the correctness of the metatest is presented. The properties of the generator were also studied via 9 simulation like experiments (entropy of the generated sequence, compression factor, Monte Carlo computation of various constants, serial correlation etc.). All the tests show very good properties of the generator. A weak point is the initial seed of \(T\) (the generator seems not to be sensitive to it). Some hints are given. Another problem is the test of the length of the period of the generator. It tends to be quite expensive.