Lower bounds for the discrepancy of inversive congruential pseudorandom numbers
Harald Niederreiter · Mathematics of Computation · 1990
The inversive congruential method is a uniform pseudorandom number generator which was introduced recently. For a prime modulus p the discrepancy D p ( k ) D_p^{(k)} of k -tuples of successive pseudorandom numbers generated by this method determines the statistical independence properties of these pseudorandom numbers. It was shown earlier by the author that \[ D p ( k ) = O ( p − 1 / 2 ( log p ) k ) for 2 ≤ k > p . D_p^{(k)} = O({p^{ - 1/2}}{(\log p)^k})\quad {\text {for}}\;2 \leq k > p. \] Here it is proved that this bound is essentially best possible. In fact, for a positive proportion of the admissible parameters in the inversive congruential method the discrepancy D p ( k ) D_p^{(k)} is at least of the order of magnitude p − 1 / 2 {p^{ - 1/2}} for all k ≥ 2 k \geq 2 .