The multiple-recursive matrix method for pseudorandom number generation (Q1344090)

The author carries out an in-depth analysis of the multiple-recursive matrix method for uniform pseudorandom number generation introduced by his earlier work [Linear Algebra Appl. 192, 301-328 (1993)]. Let \(k\) and \(m\) be positive integers. Let \(\mathbb{F}_ p\) be the finite field of order \(p\), which is identified with the set \(\{0,1, \ldots,p-1\}\) of integers where \(p\) is prime. Suppose that \(A_ 0, A_ 1, \ldots, A_{k-1}\) are \(m\times m\) matrices over \(\mathbb{F}_ p\), and that \(A_ 0\) is nonsingular. We generate a sequence \(\vec z_ 0, \vec z_ 1, \ldots\) of row vectors from \(\mathbb{F}^ m_ p\) by choosing initial vectors \(\vec z_ 0, \vec z_ 1, \ldots, \vec z_{k-1}\in \mathbb{F}^ m_ p\) that are not all \(\vec 0\) and using the \(k\)-th order vector recursion \(\vec z_{n+k}= \sum_{h=0}^{k-1} \vec z_{n+h} A_ h\), \(n=0,1, \ldots\;\). Let \(\vec z_ n= (z_ n^{(1)}, \ldots, z_ n^{(m)})\), \(n=0,1, \ldots\;\). Then we obtain the pseudo-random numbers \[ x_ n= \sum_{j=1}^ m z_ n^{(j)} p^{-j}\in [0,1), \qquad n=0,1, \ldots\;. \] The author proves that for any \(p\), \(k\) and \(m\) there exists a choice of parameters such that the sequence \((x_ n )_{n\geq 0}\) has the least period length \(\text{per} (x_ n)= p^{km} -1\). Therefore the multiple-recursive matrix method is much more efficient than the GFSR method, which can only generate a sequence \((y_ n )_{n\geq 0}\) having \(\text{per} (y_ n)= p^ k-1\). He also shows that if \(\text{per} (x_ n)= p^{km}-1\) and \(s>k\), then the \(p^{km}\) points \(\vec 0,\vec x_ 0, \ldots, \vec x_{p^{km}-2}\) in \([0,1)^ s\) form a \((t, km, s)\)-net in base \(p\) with \(t= km- r^{(s)} (B, \sigma)\), where \(\vec x_ n= (x_ n, x_{n+1}, \ldots, x_{n+s-1})\), \(n=1,2, \ldots\), and \(r^{(s)} (B, \sigma)\) is the figure of merit (a positive integer assessing the suitability of parameters in the multiple-recursive matrix method). Furthermore, he also studies the performance of the sequence \((\vec x_ n )_{n\geq 0}\) under the \(s\)- dimensional serial test, where \(s>k\) and \(\text{per} (x_ n)= p^{km} -1\).