On the adequacy of pseudy-random number generators (or: How big a period do we need?) (Q1084828)

Let G be a pseudorandom number generator generating a permutation of numbers 1,2,...,N-1 (e.g. a linear congruential generator). The randomness of G can be tested by the following procedure. The randomness hypothesis is rejected if no number occurs more than once in the sequence of the length K(N). It is shown that \(K^ 2(N)/N\) should be small (otherwise the hypothesis is rejected with great probability). So in common situations we can use surprisingly short sequences generated by G. Some further remarks on the combinatorial properties of the sequence generated by G are given.