Random number generation with the recursion Xt = Xt−3p ⊕ Xt−3q

摘要

A generalized feedback shift register (GFSR) algorithm proposed by Lewis and Payne (1973) uses a primitive trinomial to generate a sequence of pseudorandom numbers. We propose a similar algorithm which uses a primitive polynomial with many nonzero terms, but generates a number as fast as the original GFSR algorithm. Our sequence is guaranteed to be equidistributed in higher dimensions and to have a good autocorrelation property. Extensive statistical tests have been performed on the sequences generated by our algorithm and the results were quite satisfactory.