Upper bounds for the Beyer ratios of linear congruential generators

摘要

The most common pseudorandom number generators are the linear congruential generators. It is well known that the set of all vectors of consecutive pseudorandom numbers determines a lattice if the linear congruential generator has maximal period length. Therefore linear congruential generators are often assessed by the ratio between the shortest and the longest vector of the Minkowski reduced basis, the so-called Beyer ratio. Generally the Minkowski reduced basis can only be determined with great computational effort. Therefore bounds for the Beyer ratio are of great interest. For mixed congruential generators a lower bound for the longest vector and an upper bound for the shortest vector of the Minkowski reduced basis are determined. This leads to an upper bound for the Beyer ratio which depends only on the prime factorization of the modulus.