Computation of critical distances within multiplicative congruential pseudorandom number sequences (Q1185973)

Let \(y_ 1,y_ 2,y_ 3,\dots\) be a sequence of pseudorandom numbers generated by a multiplicative congruential generator \(G\). The last two authors discovered that there are \(s\) so-called critical shifts such that the points \((y_ n,y_{n+s})\) concentrate on few parallel lines. So \((y_ n,y_{n+s})\), \(n=1,2,3,\ldots\) are strongly correlated and the sequences \(y_ 1,y_ 2,\dots,y_ m\) with \(m>s\) should not be used. The authors present the algorithm computing critical shifts. No detailed proof is presented. The algorithm was used on a generator from IBM library \(y_{n+1}=7^ 5y_ n\) \(\bmod (2^{31}-1)\). The smallest critical shift of it is 642551. The generator \(y_ n=71971110957370*y_{n-1}\) \(\bmod(2^{47}- 115)\) has the least shift greater than \(10^{10}\).