Symmetry properties of multiple recursive random number generators in full period and spectral test (Q1399738)

Multiple recursive \(k\)-th order random number generators (MRG) of the form \[ X_n \equiv a_1 X_{n-1} + a_2 X_{n-2} + \ldots + a_k X_{n-k} \pmod m \] are considered for \(n \geq k\), where \(m\) is the modulus usually choosen to be the largest prime number that fits in a computer word. The main problem is to find an optimal (ideal) vector of multipliers among those which produce random numbers of full period, using the spectral test as a criterion. Every MRG is associated with another MRG \[ Y_n \equiv -a_1 Y_{n-1} + (-1)^2 a_2 Y_{n-2} + \ldots + (-1)^k a_k Y_{n-k} \pmod m, \] which attains a full period of \(m^k -1\) provided that so does the original MRG for the cases where either \(k\) is even or \((m-1)\) is a multiple of \(4\). This is one symmetry property which is proven. The other one is that the respective spectral values of both generators are equal. It allows to reduce by half the computational effort required in testing full period and spectral test.