×

Twisted GFSR generators. (English) Zbl 0849.94014

The authors propose a new pseudorandom number generator named the twisted generalized feedback shift register (TGFSR) generator and based on the linear recurrence \({\mathbf x}_{\ell+ n}:= {\mathbf x}_{\ell+ m} \oplus {\mathbf x}_\ell A\) \((\ell= 0, 1, \dots)\), where \({\mathbf x}_\ell\) is a word with components 0 or 1 of size \(w\) and is also regarded as a row vector over GF(2), \(A\) is a \(w\times w\) matrix over GF(2), and \(\oplus\) denotes the bitwise exclusive-or operation. This algorithm is a slightly but essentially modified version of the GFSR algorithm suggested by T. G. Lewis and W. H. Payne [J. ACM 20, 456-468 (1973; Zbl 0266.65009)]. The theoretical analysis and statistical tests given by the authors in this paper show that the TGFSR algorithm not only retains the well-known merits of the GFSR algorithm but also improves the original algorithm in many areas, and so the new generator is most suitable for simulation of a large distributive system, which requires a number of mutually independent pseudorandom number generators with compact size.

MSC:

94A55 Shift register sequences and sequences over finite alphabets in information and communication theory
65C10 Random number generation in numerical analysis
11K45 Pseudo-random numbers; Monte Carlo methods
PDFBibTeX XMLCite
Full Text: DOI Link Link