Optimal characteristic polynomials for digital multistep pseudorandom numbers (Q1822442)

Digital k-step pseudorandom numbers are obtained from a sequence \(y_ 0,y_ 1,..\). of bits generated by the recursion \(y_{n+k}\equiv \sum ^{k-1}_{i=0}b_ iy_{n+i} mod 2\) for \(n=0,1,..\). by setting \(x_ n=\sum ^{k}_{j=1}y_{kn+j-1}2^{-j}\) for \(n=0,1..\).. It is assumed that the initial values \(y_ 0,y_ 1,...,y_{k-1}\) are not all 0, that \(k\geq 2\) and \(\gcd (k,2^ k-1)=1\), and that the characteristic polynomial \(f(x)=x^ k-\sum ^{k-1}_{i=0}b_ ix^ i\) of the recursion is primitive over the binary field \(F_ 2\). According to earlier work of the second author [Sitzungsber. Österr. 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^ k\). The paper under review describes a systematic method of constructing primitive polynomials f over \(F_ 2\) with L(f)\(\leq 2\), which is based on results of the second author [Monatsh. Math. 103, 269-288 (1987)]. Tables of such polynomials for degrees \(k\leq 64\) are included.