The Runs Up-and-Down Performance of Tausworthe Pseudo-Random Number Generators

Abstract

Any Tausworthe generator based upon a primitive trinomial over GF(2), xp + xq + 1, can be represented as a simple linear recurrence in GF(2P). For a generator producing a sequence of p-bit pseudo-random numbers, (p, 2p -1) = 1, which is guaranteed by Tausworthe's theory to be 1-distributed, the recurrence may reveal combinatorial relationships implying a poor runs up-and-down performance. This occurs when q is small, too near p/2, or nearly equal to p. Elementary but tedious combinatorics then enable the frequencies of runs of given length, either up or down, to be predicted quantitatively. Empirical studies strikingly confirm these predictions.