\input zb-basic
\input zb-ioport
\iteman{io-port 04003339}
\itemau{Mullen, G.L.; Niederreiter, H.}
\itemti{Optimal characteristic polynomials for digital multistep pseudorandom numbers.}
\itemso{Computing 39, 155-163 (1987).}
\itemab
Digital k-step pseudorandom numbers are obtained from a sequence $y\sb 0,y\sb 1,..$. of bits generated by the recursion $y\sb{n+k}\equiv \sum \sp{k-1}\sb{i=0}b\sb iy\sb{n+i} mod 2$ for $n=0,1,..$. by setting $x\sb n=\sum \sp{k}\sb{j=1}y\sb{kn+j-1}2\sp{-j}$ for $n=0,1..$.. It is assumed that the initial values $y\sb 0,y\sb 1,...,y\sb{k-1}$ are not all 0, that $k\ge 2$ and $\gcd (k,2\sp k-1)=1$, and that the characteristic polynomial $f(x)=x\sp k-\sum \sp{k-1}\sb{i=0}b\sb ix\sp i$ of the recursion is primitive over the binary field $F\sb 2$. According to earlier work of the second author [Sitzungsber. \"Osterr. Akad. Wiss. Math.-Naturwiss. Kl. Abt. II 195, 109-138 (1986)], digital k-step pseudorandom numbers pass the serial test for statistical independence of pairs precisely if L(f) is small, where L(f) is the maximum degree of the partial quotients in the continued fraction expansion of $f(x)/x\sp k$. The paper under review describes a systematic method of constructing primitive polynomials f over $F\sb 2$ with L(f)$\le 2$, which is based on results of the second author [Monatsh. Math. 103, 269-288 (1987)]. Tables of such polynomials for degrees $k\le 64$ are included.
\itemrv{~}
\itemcc{}
\itemut{digital multistep pseudorandom numbers; serial test; continued fraction expansion; primitive polynomials; tables}
\itemli{doi:10.1007/BF02310104}
\end