Lower bounds for the discrepancy of inversive congruential pseudorandom numbers

Abstract:

The inversive congruential method is a uniform pseudorandom number generator which was introduced recently. For a prime modulus p the discrepancy $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})\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)}$ is at least of the order of magnitude ${p^{ - 1/2}}$ for all $k \geq 2$.